Search

In this paper, we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics (also known as the Gibbs sampler). The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This paper deviates from the standard formulation of graphical model learning in the literature, where one assumes access to independent identically distributed samples from the distribution. Much of the research on graphical model learning has been directed toward finding algorithms with low computational cost. As the main result of this paper, we establish that the problem of reconstructing binary pairwise graphical models is computationally tractable when we observe the Glauber dynamics. Specifically, we show that a binary pairwise graphical model on p nodes with maximum degree d can be learned in time f(d)p^2\log p , for a function f(d) defined explicitly in this paper, using nearly the information-theoretic minimum number of samples. [ABSTRACT FROM AUTHOR]

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization, even with huge size, can be solved very efficiently through the standard optimization algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization-based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization-based formulation and recover the true low-rank matrix. We study the local geometry of a properly regularized objective and prove that any stationary point in a certain local region is globally optimal. A major difference of this paper from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis. [ABSTRACT FROM PUBLISHER]

The history of infections and epidemics holds famous examples where understanding, containing, and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV, and most computer viruses spread person to person, device to device, and through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper, we study two fundamental questions of detection. First, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a random illness operating independently of any contact network (e.g., seasonal allergies)? Second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread—the causative network—without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions that networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the $d$ -dimensional grid, and the Erdös-Renyi graphs. [ABSTRACT FROM AUTHOR]

In this paper, an application of the theoretical algebraic notion of a separable ring extension in the realm of cyclic convolutional codes or, more generally, ideal codes, is investigated. It is worked under very mild conditions that cover all previously known as well as new non-trivial examples. It is proved that ideal codes are direct summands, as left ideals, of the underlying non-commutative algebra, in analogy with cyclic block codes. This implies, in particular, that they are generated by a non-commutative idempotent polynomial. Hence, by using a suitable separability element, an efficient algorithm for computing one of such idempotents is designed. We show that such an idempotent generator polynomial can be used to get information on the free distance of the convolutional code. [ABSTRACT FROM AUTHOR]

In this paper, we design novel distributed scheduling algorithms for multiuser multiple-input multiple-output systems and evaluate the resulting system capacity analytically. In particular, we consider algorithms which do not require sending channel state information to a central processing unit, nor do they require communication between the users themselves, yet, the resulting capacity closely approximates that of a centrally controlled system, which is able to schedule the strongest user in each time-slot. In other words, multiuser diversity is achieved in a distributed fashion. Our analysis is based on a novel application of the point-process approximation. This technique, besides tackling previously suggested models successfully, allows an analytical examination of new models, such as nonhomogeneous cases (nonidentically distributed users) or various quality of service considerations. This results in asymptotically exact expressions for the capacity of the system under these schemes, solving analytically problems which to date had been open. Possible applications include, but are not limited to, modern 4G networks, such as 3GPP LTE, or random access protocols. [ABSTRACT FROM PUBLISHER]

Consider two remote nodes having binary sequences $X$ and Y$ , respectively. Y$ is an edited version of , where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with Y$ to reconstruct X$ with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is , where $n$ is the length of $X$ . We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of $O(n)$ arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way algorithm based on the single-deletion correcting channel codes of Varshamov and Tenengolts. We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms. [ABSTRACT FROM PUBLISHER]

This paper builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and Lercier in 2006. We make several contributions. The first contribution uses a divisibility and smoothness technique and goes on to develop a sieving method based on the technique. This leads to significant practical efficiency improvements in the descent phase and also provides improvement to Joux’s pinpointing technique. The second contribution is a detailed analysis of the degree of freedom and the use of a walk technique in the descent phase of the algorithm. Such analysis shows that it is possible to compute discrete logarithms over certain fields, which are excluded by the earlier analyses performed by Joux and Lercier (2006) and Joux (2013). In concrete terms, we present computations of discrete logs for fields with 16 and 19-bit prime characteristic. We also provide concrete analysis of the effectiveness of the FFS algorithm for certain fields of characteristic ranging from 16 to 32-bit primes. The final contribution is to perform a complete asymptotic analysis of the FFS algorithm for fields \mathbb FQ with p=LQ(1/3,c) . This closes gaps and corrects errors in the analysis earlier performed by Joux–Lercier and Joux and also provides new insights into the asymptotic behavior of the algorithm. [ABSTRACT FROM AUTHOR]

Recently, network error correction coding (NEC) has been studied extensively. Several bounds in classical coding theory have been extended to NEC, especially the Singleton bound. In this paper, following the research line using the extended global encoding kernels proposed by Zhang in 2008, the refined Singleton bound of NEC can be proved more explicitly. Moreover, we give a constructive proof of the attainability of this bound and indicate that the required field size for the existence of network maximum distance separable (MDS) codes can become smaller further. By this proof, an algorithm is proposed to construct general linear network error correction codes including the linear network error correction MDS codes. Finally, we study the error correction capability of random linear NEC. Motivated partly by the performance analysis of random linear network coding, we evaluate the different failure probabilities defined in this paper in order to analyze the performance of random linear NEC. Several upper bounds on these probabilities are obtained and they show that these probabilities will approach to zero as the size of the base field goes to infinity. Using these upper bounds, we slightly improve on the probability mass function of the minimum distance of random linear network error correction codes in a paper by Balli and colleagues, as well as the upper bound on the field size required for the existence of linear network error correction codes with degradation at most d. [ABSTRACT FROM AUTHOR]

This paper develops a distributed algorithm for rate allocation in wireless networks that achieves the same throughput region as optimal centralized algorithms. This cross-layer algorithm jointly performs medium access control and physical-layer rate adaptation. The paper establishes that this algorithm is throughput-optimal for general rate regions. In contrast to on-off scheduling, rate allocation enables optimal utilization of physical-layer schemes by scheduling multiple rate levels. The algorithm is based on local queue-length information, and thus the algorithm is of significant practical value. An important application of this algorithm is in multiple-band multiple-radio throughput-optimal distributed scheduling for white-space networks. [ABSTRACT FROM AUTHOR]

This paper provides proofs of the rate stability, Harris recurrence, and \varepsilon-optimality of carrier sense multiple access (CSMA) algorithms where the random access (or backoff) parameter of each node is adjusted dynamically. These algorithms require only local information and they are easy to implement. The setup is a network of wireless nodes with a fixed conflict graph that identifies pairs of nodes whose simultaneous transmissions conflict. The paper studies two algorithms. The first algorithm schedules transmissions to keep up with given arrival rates of packets. The second algorithm controls the arrivals in addition to the scheduling and attempts to maximize the sum of the utilities, in terms of the rates, of the packet flows at different nodes. For the first algorithm, the paper proves rate stability for strictly feasible arrival rates and also Harris recurrence of the queues. For the second algorithm, the paper proves the \varepsilon-optimality in terms of the utilities of the allocated rates. Both algorithms are iterative and we study two versions of each of them. In the first version, both operate with strictly local information but have relatively weaker performance guarantees; under the second version, both provide stronger performance guarantees by utilizing the additional information of the number of nodes in the network. [ABSTRACT FROM AUTHOR]

A denoising algorithm seeks to remove noise, errors, or perturbations from a signal. Extensive research has been devoted to this arena over the last several decades, and as a result, todays denoisers can effectively remove large amounts of additive white Gaussian noise. A compressed sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired using a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop an extension of the approximate message passing (AMP) framework, called denoising-based AMP (D-AMP), that can integrate a wide class of denoisers within its iterations. We demonstrate that, when used with a high-performance denoiser for natural images, D-AMP offers the state-of-the-art CS recovery performance while operating tens of times faster than competing methods. We explain the exceptional performance of D-AMP by analyzing some of its theoretical features. A key element in D-AMP is the use of an appropriate Onsager correction term in its iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove. [ABSTRACT FROM PUBLISHER]

We analyze the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications, such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis, or factor analysis. It is also important in machine learning: unsupervised representation learning can often be studied through matrix factorization. We use the tools of statistical mechanics—the cavity and replica methods—to analyze the achievability and computational tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random-independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable, in principle, in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm. [ABSTRACT FROM PUBLISHER]

In this paper, we analyze a collaborative filter that answers the simple question: What is popular amongst your “friends”? While this basic principle seems to be prevalent in many practical implementations, there does not appear to be much theoretical analysis of its performance. In this paper, we partly fill this gap. While recent works on this topic, such as the low-rank matrix completion literature, consider the probability of error in recovering the entire rating matrix, we consider probability of an error in an individual recommendation [bit error rate (BER)]. For a mathematical model introduced by Aditya in 2009 and 2011, we identify three regimes of operation for our algorithm (named Popularity Amongst Friends) in the limit as the matrix size grows to infinity. In a regime characterized by large number of samples and small degrees of freedom (defined precisely for the model in the paper), the asymptotic BER is zero; in a regime characterized by large number of samples and large degrees of freedom, the asymptotic BER is bounded away from 0 and 1/2 (and is identified exactly except for a special case); and in a regime characterized by a small number of samples, the algorithm fails. We then compare these results with the performance of the optimal recommender. We also present numerical results for the MovieLens and Netflix datasets. We discuss the empirical performance in light of our theoretical results and compare with an approach based on low-rank matrix completion. [ABSTRACT FROM AUTHOR]

Autocorrelation sidelobes are a form of self-noise that reduce the effectiveness of phase coding in radar and communication systems. The merit factor is a well-known measure related to the autocorrelation sidelobe energy of a sequence. In this paper an equation is derived that allows the change in the merit factor of a binary sequence to be computed for all single-element changes with O(N\log N) operations, where N is the sequence length. The approach is then extended to multiple-element changes, allowing the merit factor change to be calculated with an additional O(Ns^{3}) operations, where Ns is the number of changed elements, irrespective of sequence length. The multiple-element calculations can be used to update the single-element calculations so that in iterative use only O(N) operations are required per element change to keep the single-element calculations current. A steep descent algorithm (a variation on the steepest descent method) employing these two techniques was developed and applied to quarter-rotated, periodically extended Legendre sequences, producing optimized sequences with an apparent asymptotic merit factor of approximately 6.3758, modestly higher than the best known prior result of approximately 6.3421. Modified Jacobi sequences improve after steep descent to an approximate asymptotic merit factor of 6.4382. Three-prime and four-prime Jacobi sequences converge very slowly making a determination difficult but appear to have a higher post-steep-descent asymptotic merit factor than Legendre or modified Jacobi sequences. [ABSTRACT FROM AUTHOR]

We consider the orthogonal matching pursuit (OMP) algorithm for the recovery of a high-dimensional sparse signal based on a small number of noisy linear measurements. OMP is an iterative greedy algorithm that selects at each step the column, which is most correlated with the current residuals. In this paper, we present a fully data driven OMP algorithm with explicit stopping rules. It is shown that under conditions on the mutual incoherence and the minimum magnitude of the nonzero components of the signal, the support of the signal can be recovered exactly by the OMP algorithm with high probability. In addition, we also consider the problem of identifying significant components in the case where some of the nonzero components are possibly small. It is shown that in this case the OMP algorithm will still select all the significant components before possibly selecting incorrect ones. Moreover, with modified stopping rules, the OMP algorithm can ensure that no zero components are selected. [ABSTRACT FROM AUTHOR]

In this paper we analyze the interval algorithm for random number generation proposed by Han and Hoshi using the expression of real numbers on the interval [0,1). We first establish an explicit representation of the interval algorithm with the representation of real numbers on the interval [0,1) based on number systems. Next, using the expression of the interval algorithm, we give a rigorous analysis of the interval algorithm. We discuss the difference between the expected number of the coin tosses in the interval algorithm and their upper bound derived by Han and Hoshi and show that it can be characterized explicitly with the established expression of the interval algorithm. [ABSTRACT FROM PUBLISHER]

“Approximate message passing” (AMP) algorithms have proved to be effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper, we provide rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed Gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with a large number of short cycles in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory. [ABSTRACT FROM AUTHOR]

This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing architecture and a dynamic routing-scheduling-coding strategy are introduced for serving multiple sessions when linear network coding is allowed across sessions. This policy provides a novel extension to the class of back-pressure policies by incorporating inter-session coding decisions via simple rules on the relevant queue-length levels. Despite the fact that the capacity region of inter-session coding is a challenging open problem, in this paper, we prove that our algorithm can support any set of rates in a nontrivial characterized region of achievable rates. In addition to its practical implications, this work also provides a theoretical framework in which the gains of inter-session network coding and pure routing can be compared. [ABSTRACT FROM AUTHOR]

The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. An algorithm, which finds an optimal quantizer, in the sense of maximizing mutual information between the channel input and quantizer output is given. This result holds for arbitrary channels, in contrast to previous results for restricted channels or a restricted number of quantizer outputs. In the worst case, the algorithm complexity is cubic \( M^{3}\) in the number of channel outputs \( M\) . Optimality is proved using the theorem of Burshtein, Della Pietra, Kanevsky, and Nádas for mappings, which minimize average impurity for classification and regression trees. [ABSTRACT FROM PUBLISHER]

We consider some computationally efficient and provably correct algorithms with near-optimal sample complexity for the problem of noisy nonadaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be sparse. We consider nonadaptive randomly pooling measurements, where pools are selected randomly and independently of the test outcomes. We also consider a model where noisy measurements allow for both some false negative and some false positive test outcomes (and also allow for asymmetric noise, and activation noise). We consider three classes of algorithms for the group testing problem (we call them specifically the coupon collector algorithm, the column matching algorithms, and the LP decoding algorithms—the last two classes of algorithms (versions of some of which had been considered before in the literature) were inspired by corresponding algorithms in the compressive sensing literature. The second and third of these algorithms have several flavors, dealing separately with the noiseless and noisy measurement scenarios. Our contribution is novel analysis to derive explicit sample-complexity bounds—with all constants expressly computed—for these algorithms as a function of the desired error probability, the noise parameters, the number of items, and the size of the defective set (or an upper bound on it). We also compare the bounds to information-theoretic lower bounds for sample complexity based on Fano's inequality and show that the upper and lower bounds are equal up to an explicitly computable universal constant factor (independent of problem parameters). [ABSTRACT FROM AUTHOR]

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressed sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimension n). The asymptotic analysis predicts the fraction of unverified signal elements at each iteration \ell in the asymptotic regime where n\rightarrow\infty. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of nontrivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function of \ell. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values of n. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is more accurate and simpler to implement. [ABSTRACT FROM PUBLISHER]

Compressed sensing with sparse frame representations is seen to have much greater range of practical applications than that with orthonormal bases. In such settings, one approach to recover the signal is known as \ell 1-analysis. We expand in this paper the performance analysis of this approach by providing a weaker recovery condition than existing results in the literature. Our analysis is also broadly based on general frames and alternative dual frames (as analysis operators). As one application to such a general-dual-based approach and performance analysis, an optimal-dual-based technique is proposed to demonstrate the effectiveness of using alternative dual frames as analysis operators. An iterative algorithm is outlined for solving the optimal-dual-based \ell 1-analysis problem. The effectiveness of the proposed method and algorithm is demonstrated through several experiments. [ABSTRACT FROM PUBLISHER]

Absorbing sets, a class of combinatorial structures of the Tanner graph representation of a low-density parity-check (LDPC) code, are known to influence the performance of the code under message passing iterative decoding. In this paper, we study the smallest absorbing sets of LDPC codes constructed from projective planes and Euclidean planes. The lower bounds on the parameters of smallest absorbing sets given by Dolecek are proven to be tight for these two families of LDPC codes. We also analyze the combinatorial properties of the smallest absorbing sets and give conditions necessary and sufficient for a set of bit nodes in the Tanner graph to be a smallest absorbing set. For LDPC codes from projective planes, we further give a condition necessary and sufficient for a smallest absorbing set to be a fully absorbing set. In addition, we show that these smallest absorbing sets are asymptotically not stable, which may explain to some extent the good performance as well as the low error floor expectation of these two families of LDPC codes. [ABSTRACT FROM PUBLISHER]

This paper builds on Mittelholzer and Lahtonen's study of group codes for the Gaussian channel based on reflection groups. A careful analysis of the action of a reflection group on its roots leads to the development of improved methods for encoding and decoding. The new algorithm is proved to achieve maximum likelihood decoding. The complexity of decoding is analyzed, and it is shown that a proper choice of the sequence of subgroups used in the algorithm can yield significant gains in the efficiency of decoding. [ABSTRACT FROM AUTHOR]

Inference problems in graphical models can be represented as a constrained optimization of a free-energy function. In this paper, we treat both forms of probabilistic inference, estimating marginal probabilities of the joint distribution and finding the most probable assignment, through a unified message-passing algorithm architecture. In particular we generalize the belief propagation (BP) algorithms of sum-product and max-product and tree-reweighted (TRW) sum and max product algorithms (TRBP) and introduce a new set of convergent algorithms based on “convex-free-energy” and linear-programming (LP) relaxation as a zero-temperature of a convex-free-energy. The main idea of this work arises from taking a general perspective on the existing BP and TRBP algorithms while observing that they all are reductions from the basic optimization formula of f+\sumihi where the function f is an extended-valued, strictly convex but nonsmooth and the functions hi are extended-valued functions (not necessarily convex). We use tools from convex duality to present the “primal-dual ascent” algorithm which is an extension of the Bregman successive projection scheme and is designed to handle optimization of the general type f+\sumihi. We then map the fractional-free-energy variational principle for approximate inference onto the optimization formula above and introduce the “norm-product” message-passing algorithm. Special cases of the norm-product include sum-product and max-product (BP algorithms), TRBP and NMPLP algorithms. When the fractional-free-energy is set to be convex (convex-free-energy) the norm-product is globally convergent for the estimation of marginal probabilities and for approximating the LP-relaxation. We also introduce another branch of the norm-product which arises as the “zero-temperature” of the convex-free-energy which we refer to as the “convex-max-product”. The convex-max-product is convergent (unlike max-product) and aims at solving the LP- relaxation. [ABSTRACT FROM PUBLISHER]

Existing works on distributed consensus explore linear iterations based on reversible Markov chains, which contribute to the slow convergence of the algorithms. It has been observed that by overcoming the diffusive behavior of reversible chains, certain nonreversible chains lifted from reversible ones mix substantially faster than the original chains. In this paper, the idea of Markov chain lifting is studied to accelerate the convergence of distributed consensus, and two general pseudoalgorithms are presented. These pseudoalgorithms are then instantiated through a class of location-aided distributed averaging (LADA) algorithms for wireless networks, where nodes' coarse location information is used to construct nonreversible chains that facilitate distributed computing and cooperative processing. Our first LADA algorithm is designed for grid networks; for a k\times k grid network, it achieves an \epsilon -averaging time of O(k\log (\epsilon ^-1)). Based on this algorithm, in a wireless network with transmission range r, an \epsilon -averaging time of O(r^-1\log (\epsilon ^-1)) can be attained through a centralized algorithm. Subsequently, a distributed LADA algorithm is presented, achieving the same scaling law in averaging time as the centralized scheme in wireless networks for all r satisfying the connectivity requirement; the constructed chain also attains the optimal scaling law in terms of an important mixing metric, the fill time, in its class. Finally, a cluster-based LADA algorithm is proposed, which, requiring no central coordination, provides the additional benefit of reduced message complexity compared with the distributed LADA algorithm. [ABSTRACT FROM PUBLISHER]

We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f\in\BBC^N and their approximate Fourier coefficients in running time and sample complexity polynomial in \log N, L1(\widehat f)/\Vert\widehat f\Vert2, and 1/\tau, where the significant frequencies are those occupying at least a \tau-fraction of the energy of the signal, and L1(\widehat f) denotes the L1-norm of the Fourier transform of f. Furthermore, the algorithm is robust to additive random noise. This strictly extends the class of compressible/Fourier sparse signals efficiently handled by previous deterministic algorithms for signals in \BBC^N. As a central tool, we prove there is a deterministic algorithm that takes as input N, \varepsilon and an arithmetic progression P in \BBZN, runs in time polynomial in \ln N and 1/\varepsilon, and returns a set AP that \varepsilon-approximates P in \BBZN in the sense that \vert\mathop\BBEx\in APe^{2\pi i\omega x/N}-\mathop\BBEx\in Pe^{2\pi i\omega x/N}\vert <\varepsilon for all \omega=0,\ldots, N-1. In other words, we show there is an explicit construction of sets AP of size polynomial in \ln N and 1/\varepsilon that \varepsilon-approximate given arithmetic progressions P in \BBZN. This extends results on small-bias sets, which are sets approximating the entire domain, to sets approximating a given arithmetic progression; this result may be of independent interest. [ABSTRACT FROM PUBLISHER]

Linear programming (LP) decoding for low-density parity-check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance—coming close to that of iterative decoding algorithms—and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05 fraction of correctable errors for rate-½ codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors. [ABSTRACT FROM AUTHOR]

We present a method to construct low-density parity-check (LDPC) codes with low error floors on the binary symmetric channel. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the trapping set ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum–product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four cycles. [ABSTRACT FROM AUTHOR]

We present a new lossy compressor for finite-alphabet sources. For coding a sequence x^n, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence x^n and a linear function of its k^th order empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to find the sequence with minimum cost. We identify a choice of the coefficients used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance for any stationary ergodic source, in the limit of large n, provided that k increases as o(\log n). Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied. [ABSTRACT FROM AUTHOR]

Given a large number of basis functions that can be potentially more than the number of samples, we consider the problem of learning a sparse target function that can be expressed as a linear combination of a small number of these basis functions. We are interested in two closely related themes: numeration="bullet" continuation="restarts" feature selection, or identifying the basis functions with nonzero coefficients; [ABSTRACT FROM AUTHOR]

Coherent network error correction is the error-control problem in network coding with the knowledge of the network codes at the source and sink nodes. With respect to a given set of local encoding kernels defining a linear network code, we obtain refined versions of the Hamming bound, the Singleton bound, and the Gilbert–Varshamov bound for coherent network error correction. Similar to its classical counterpart, this refined Singleton bound is tight for linear network codes. The tightness of this refined bound is shown by two construction algorithms of linear network codes achieving this bound. These two algorithms illustrate different design methods: one makes use of existing network coding algorithms for error-free transmission and the other makes use of classical error-correcting codes. The implication of the tightness of the refined Singleton bound is that the sink nodes with higher maximum flow values can have higher error correction capabilities. [ABSTRACT FROM PUBLISHER]

We consider the problem of designing a fair scheduling algorithm for discrete-time constrained queuing networks. Each queue has dedicated exogenous packet arrivals. There are constraints on which queues can be served simultaneously. This model effectively describes important special instances like network switches, interference in wireless networks, bandwidth sharing for congestion control and traffic scheduling in road roundabouts. Fair scheduling is required because it provides isolation to different traffic flows; isolation makes the system more robust and enables providing quality of service. Existing work on fairness for constrained networks concentrates on flow based fairness. As a main result, we describe a notion of packet based fairness by establishing an analogy with the ranked election problem: packets are voters, schedules are candidates, and each packet ranks the schedules based on its priorities. We then obtain a scheduling algorithm that achieves the described notion of fairness by drawing upon the seminal work of Goodman and Markowitz (1952). This yields the familiar Maximum Weight (MW) style algorithm. As another important result, we prove that the algorithm obtained is throughput optimal. There is no reason a priori why this should be true, and the proof requires nontraditional methods. [ABSTRACT FROM PUBLISHER]

We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L\,\times\,L coding matrices that play a similar role as coding coefficients in scalar coding. We start our work by extending the algebraic framework developed for multicasting over graphs by Koetter and Medard to include operations over matrices; we build on this generalized framework, to provide a new approach for both scalar and vector code design which attempts to minimize the employed field size and employed vector length, while selecting the coding operations. Our algorithms also lead as a special case to network code designs that employ structured matrices. [ABSTRACT FROM AUTHOR]

We study ensembles of codes on graphs (generalized low-density parity-check, or LDPC codes) constructed from random graphs and fixed local constrained codes, and their extension to codes on hypergraphs. It is known that the average minimum distance of codes in these ensembles grows linearly with the code length. We show that these codes can correct a linearly growing number of errors under simple iterative decoding algorithms. In particular, we show that this property extends to codes constructed by parallel concatenation of Hamming codes and other codes with small minimum distance. Previously known results that proved this property for graph codes relied on graph expansion and required the choice of local codes with large distance relative to their length. [ABSTRACT FROM AUTHOR]

We present new additive Fast Fourier Transform (FFT) algorithms based on Taylor expansions over finite fields of characteristic two. The new algorithms improve previous approaches by Wang and Zhu (1988), Cantor (1989), and von zur Gathen and Gerhard (1996). [ABSTRACT FROM PUBLISHER]

We present a new recovery analysis for a standard compressed sensing algorithm, Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2008), which considers the fixed points of the algorithm. In the context of arbitrary measurement matrices, we derive a sufficient condition for the convergence of IHT to a fixed point and a necessary condition for the existence of fixed points. These conditions allow us to perform a sparse signal recovery analysis in the deterministic noiseless case by implying that the original sparse signal is the unique fixed point and limit point of IHT, and in the case of Gaussian measurement matrices and noise by generating a bound on the approximation error of the IHT limit as a multiple of the noise level. By generalizing the notion of fixed points, we extend our analysis to the variable stepsize Normalised IHT (Blumensath and Davies, 2010). For both stepsize schemes, we obtain lower bounds on asymptotic phase transitions in a proportional-dimensional framework, quantifying the sparsity/undersampling tradeoff for which recovery is guaranteed. Exploiting the reasonable average-case assumption that the underlying signal and measurement matrix are independent, comparison with previous results within this framework shows a substantial quantitative improvement. [ABSTRACT FROM AUTHOR]

We consider the problem of nonadaptive noiseless group testing of N items of which K are defective. We describe four detection algorithms, the \tt COMP algorithm of Chan et al. , two new algorithms, \tt DD and \tt SCOMP , which require stronger evidence to declare an item defective, and an essentially optimal but computationally difficult algorithm called \tt SSS . We consider an important class of designs for the group testing problem, namely those in which the test structure is given via a Bernoulli random process. In this class of Bernoulli designs, by considering the asymptotic rate of these algorithms, we show that \tt DD outperforms \tt COMP , that \tt DD is essentially optimal in regimes where K\geq\sqrt N , and that no algorithm can perform as well as the best nonrandom adaptive algorithms when K>N^{0.35} . In simulations, we see that \tt DD and \tt SCOMP far outperform \tt COMP , with \tt SCOMP very close to the optimal \tt SSS , especially in cases with larger K$ . [ABSTRACT FROM PUBLISHER]

We consider the problem of distributed online learning with multiple players in multiarmed bandit (MAB) models. Each player can pick among multiple arms. When a player picks an arm, it gets a reward. We consider both independent identically distributed (i.i.d.) reward model and Markovian reward model. In the i.i.d. model, each arm is modeled as an i.i.d. process with an unknown distribution with an unknown mean. In the Markovian model, each arm is modeled as a finite, irreducible, aperiodic and reversible Markov chain with an unknown probability transition matrix and stationary distribution. The arms give different rewards to different players. If two players pick the same arm, there is a collision, and neither of them get any reward. There is no dedicated control channel for coordination or communication among the players. Any other communication between the users is costly and will add to the regret. We propose an online index-based distributed learning policy called \tt dUCB4 algorithm that trades off exploration versus exploitation in the right way, and achieves expected regret that grows at most as near-O(\log^2T). The motivation comes from opportunistic spectrum access by multiple secondary users in cognitive radio networks wherein they must pick among various wireless channels that look different to different users. This is the first distributed learning algorithm for multiplayer MABs with heterogeneous players (that have player-dependent rewards) to the best of our knowledge. [ABSTRACT FROM PUBLISHER]

We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization. [ABSTRACT FROM PUBLISHER]

We study how correlations in the design matrix influence Lasso prediction. First, we argue that the higher the correlations, the smaller the optimal tuning parameter. This implies in particular that the standard tuning parameters, that do not depend on the design matrix, are not favorable. Furthermore, we argue that Lasso prediction works well for any degree of correlations if suitable tuning parameters are chosen. We study these two subjects theoretically as well as with simulations. [ABSTRACT FROM AUTHOR]

We introduce a novel algorithm for decoding binary linear codes by linear programming (LP). We build on the LP decoding algorithm of Feldman and introduce a postprocessing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity. [ABSTRACT FROM AUTHOR]

We present a unique decoding algorithm of algebraic geometry (AG) codes on plane curves, Hermitian codes in particular, from an interpolation point of view. The algorithm successfully corrects errors of weight up to half of the order bound on the minimum distance of the AG code. It is the first decoding algorithm to combine some features of the interpolation-based list decoding with the performance of the syndrome decoding with the majority voting scheme. The regular structure of the algorithm allows a straightforward parallel implementation. [ABSTRACT FROM PUBLISHER]

We consider the problem of recovering a function over the space of permutations (or, the symmetric group) over n elements from given partial information; the partial information we consider is related to the group theoretic Fourier Transform of the function. This problem naturally arises in several settings such as ranked elections, multi-object tracking, ranking systems, and recommendation systems. Inspired by the work of Donoho and Stark in the context of discrete-time functions, we focus on non-negative functions with a sparse support (support size \ll domain size). Our recovery method is based on finding the sparsest solution (through \ell_0 optimization) that is consistent with the available information. As the main result, we derive sufficient conditions for functions that can be recovered exactly from partial information through \ell_0 optimization. Under a natural random model for the generation of functions, we quantify the recoverability conditions by deriving bounds on the sparsity (support size) for which the function satisfies the sufficient conditions with a high probability as n \to \infty. \ell_0 optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation, \ell_1 optimization, to find the sparsest solution. However, we show that \ell_1 optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as n \to \infty. In order to overcome this problem, we propose a novel iterative algorithm for the recovery of functions that satisfy the sufficient conditions. Finally, using an Information Theoretic framework, we study necessary conditions for exact recovery to be possible. [ABSTRACT FROM AUTHOR]

Best and Brouwer refid="ref2"/ proved that triply-shortened and doubly-shortened binary Hamming codes (which have length 2^m-4 and 2^m-3, respectively) are optimal. Properties of such codes are here studied, determining among other things parameters of certain subcodes. A utilization of these properties makes a computer-aided classification of the optimal binary one-error-correcting codes of lengths 12 and 13 possible; there are 237\thinspace610 and 117\thinspace823 such codes, respectively (with 27\thinspace375 and 17\thinspace513 inequivalent extensions). This completes the classification of optimal binary one-error-correcting codes for all lengths up to 15. Some properties of the classified codes are further investigated. Finally, it is proved that for any m \geq 4, there are optimal binary one-error-correcting codes of length 2^m-4 and 2^m-3 that cannot be lengthened to perfect codes of length 2^m-1. [ABSTRACT FROM AUTHOR]

The concept of sequential aggregate signatures (SAS), proposed by Lysyanskaya, Micali, Reyzin, and Shacham at Eurocrypt 2004, is generalized to a new primitive called sequential aggregate signed data (SASD) that tries to minimize the total amount of transmitted data, rather than just signature length. New SAS and SASD schemes are presented that offer numerous advantages over the scheme of Lysyanskaya Most importantly, the schemes can be instantiated with uncertified claw-free permutations, thereby allowing implementations based on low-exponent RSA and factoring, and drastically reducing signing and verification costs. The schemes support aggregation of signatures under keys of different lengths, and the SASD scheme even has as little as 160 bits of bandwidth overhead. Finally, a multi-signed data scheme is presented that, when compared to the state-of-the-art multi-signature schemes, is the first scheme with noninteractive signature generation not based on pairings. All of the constructions are proved secure in the random oracle model based on families of claw-free permutations. [ABSTRACT FROM PUBLISHER]

The design of optimal multi-resolution scalar quantizers using the generalized Lloyd method was proposed by Brunk and Farvardin for the case of squared error distortion. Since the algorithm details heavily rely on the quadratic expression of the error function, its extension to general error functions faces some challenges, especially at the encoder optimization step. In this work we show how these challenges can be overcome for any convex difference distortion measure, under the assumption that all quantizer cells are convex (i.e., intervals), and present an efficient algorithm for optimal encoder partition computation. The proposed algorithm is faster than the algorithm used by Brunk and Farvardin. Moreover, it can also be applied to channel-optimized and to multiple description scalar quantizer design with squared error distortion, and it outperforms in speed the previous encoder optimization algorithms proposed for these problems. [ABSTRACT FROM PUBLISHER]

We consider perfect secret key generation for a “pairwise independent network” model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Third, when a single “helper” terminal assists the remaining “user” terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a “weak” helper is shown to be sufficient for optimality. [ABSTRACT FROM AUTHOR]

We consider secret key generation for a “pairwise independent network” model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate publicly with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible, with the cooperation of any remaining terminals. Secrecy is required from an eavesdropper that has access to the public interterminal communication. A (single-letter) formula for secret key capacity brings out a natural connection between the problem of secret key generation and a combinatorial problem of maximal packing of Steiner trees in an associated multigraph. An explicit algorithm is proposed for secret key generation based on a maximal packing of Steiner trees in a multigraph; the corresponding maximum rate of Steiner tree packing is thus a lower bound for the secret key capacity. When only two of the terminals or when all the terminals seek to share a secret key, the mentioned algorithm achieves secret key capacity in which case the bound is tight. [ABSTRACT FROM PUBLISHER]