Search

Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios. [ABSTRACT FROM AUTHOR]

The Recently proposed Vector Approximate Message Passing (VAMP) algorithm demonstrates a great reconstruction potential at solving compressed sensing related linear inverse problems. VAMP provides high per-iteration improvement, can utilize powerful denoisers like BM3D, has rigorously defined dynamics and is able to recover signals measured by highly undersampled and ill-conditioned linear operators. Yet, its applicability is limited to relatively small problem sizes due to the necessity to compute the expensive LMMSE estimator at each iteration. In this work we consider the problem of upscaling VAMP by utilizing Conjugate Gradient (CG) to approximate the intractable LMMSE estimator. We propose a rigorous method for correcting and tuning CG withing CG-VAMP to achieve a stable and efficient reconstruction. To further improve the performance of CG-VAMP, we design a warm-starting scheme for CG and develop theoretical models for the Onsager correction and the State Evolution of Warm-Started CG-VAMP (WS-CG-VAMP). Additionally, we develop robust and accurate methods for implementing the WS-CG-VAMP algorithm. The numerical experiments on large-scale image reconstruction problems demonstrate that WS-CG-VAMP requires much fewer CG iterations compared to CG-VAMP to achieve the same or superior level of reconstruction. [ABSTRACT FROM AUTHOR]

Given a binary sequence with length $n$ , determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of $O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from $O(n^{2})$ to $O(n\log ^{2}n\log \log n)$ by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

The Binary Iterative Hard Thresholding (BIHT) algorithm is a popular reconstruction method for one-bit compressed sensing due to its simplicity and fast empirical convergence. Despite considerable research on this algorithm, a theoretical understanding of the corresponding approximation error and convergence rate still remains an open problem. This paper shows that the normalized version of BIHT (NBIHT) achieves an approximation error rate optimal up to logarithmic factors. More precisely, using $m$ one-bit measurements of an $s$ -sparse vector $x$ , we prove that the approximation error of NBIHT is of order $O \left ({\frac{1 }{ m }}\right)$ up to logarithmic factors, which matches the information-theoretic lower bound $\Omega \left ({\frac{1 }{ m }}\right)$ proved by Jacques, Laska, Boufounos, and Baraniuk in 2013. To our knowledge, this is the first theoretical analysis of a BIHT-type algorithm that explains the optimal rate of error decay empirically observed in the literature. This also makes NBIHT the first provable computationally-efficient one-bit compressed sensing algorithm that breaks the inverse square-root error decay rate $O \left ({\frac{1 }{ m^{1/2} }}\right)\vphantom {{\left ({\frac{1 }{ m^{1/2} }}\right)}^{'}}$. [ABSTRACT FROM AUTHOR]

In this work, we study the generalization capability of algorithms from an information-theoretic perspective. It has been shown that the expected generalization error of an algorithm is bounded from above by a function of the relative entropy between the conditional probability distribution of the algorithm’s output hypothesis, given the dataset with which it was trained, and its marginal probability distribution. We build upon this fact and introduce a mathematical formulation to obtain upper bounds on this relative entropy. Assuming that the data is discrete, we then develop a strategy using this formulation, based on the method of types and typicality, to find explicit upper bounds on the generalization error of stable algorithms, i.e., algorithms that produce similar output hypotheses given similar input datasets. In particular, we show the bounds obtained with this strategy for the case of $\epsilon $ -DP and $\mu $ -GDP algorithms. [ABSTRACT FROM AUTHOR]

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner code C0 of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the code C = C(G, C0) of length nd from approximately δ δr nd erasures in time n ⋅ poly (d2r/δ), where δ and δr are the relative distance and the r’th generalized relative distance of C0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters. [ABSTRACT FROM AUTHOR]

This paper studies a large random matrix system (LRMS) model involving an arbitrary signal distribution and forward error control (FEC) coding. We establish an area property based on the approximate message passing (AMP) algorithm. Under the assumption that the state evolution for AMP is correct for the coded system, the achievable rate of AMP is analyzed. We prove that AMP achieves the constrained capacity of the LRMS with an arbitrary signal distribution provided that a matching condition is satisfied. As a byproduct, we provide an alternative derivation for the constraint capacity of an LRMS using a proved property of AMP. We discuss realization techniques for the matching principle of binary signaling using irregular low-density parity-check (LDPC) codes and provide related numerical results. We show that the optimized codes demonstrate significantly better performance over un-matched ones under AMP. For quadrature phase shift keying (QPSK) modulation, bit error rate (BER) performance within 1 dB from the constrained capacity limit is observed. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

Phase retrieval refers to the problem of recovering a signal $ {x}_{\star }\in \mathbb {C}^{n}$ from its phaseless measurements $\text {y}_{\text {i}}=| {a}_{i}^{ \mathsf {H}} {x}_{\star }|$ , where $\{ {a}_{\text {i}}\}_{\text {i}=1}^{ {m}}$ are the measurement vectors. Spectral method is widely used for initialization in many phase retrieval algorithms. The quality of spectral initialization can have a major impact on the overall algorithm. In this paper, we focus on the model where $ {A}=[ {a}_{1},\ldots, {a}_{ {m}}]^{ \mathsf {H}}$ has orthonormal columns, and study the spectral initialization under the asymptotic setting $ {m}, {n}\to \infty $ with $ {m}/ {n}\to \delta \in (1,\infty)$. We use the expectation propagation framework to characterize the performance of spectral initialization for Haar distributed matrices. Our numerical results confirm that the predictions of the EP method are accurate for not-only Haar distributed matrices, but also for realistic Fourier based models (e.g. the coded diffraction model). The main findings of this paper are the following: 1) There exists a threshold on $\delta $ (denoted as $\delta _{ \mathrm {weak}}$) below which the spectral method cannot produce a meaningful estimate. We show that $\delta _{ \mathrm {weak}}=2$ for the column-orthonormal model. In contrast, previous results by Mondelli and Montanari show that $\delta _{ \mathrm {weak}}=1$ for the i.i.d. Gaussian model. 2) The optimal design for the spectral method coincides with that for the i.i.d. Gaussian model, where the latter was recently introduced by Luo, Alghamdi and Lu. [ABSTRACT FROM AUTHOR]

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorous a priori and a posteriori bounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments. [ABSTRACT FROM AUTHOR]

The problem of completing a large low rank matrix using a subset of revealed entries has received much attention in the last ten years. The main result of this paper gives a necessary and sufficient condition, stated in the language of graph limit theory, for a sequence of matrix completion problems with arbitrary missing patterns to be asymptotically solvable. It is then shown that a small modification of the Candès–Recht nuclear norm minimization algorithm provides the required asymptotic solution whenever the sequence of problems is asymptotically solvable. The theory is fully deterministic, with no assumption of randomness. A number of open questions are listed. [ABSTRACT FROM AUTHOR]

Compressive phase retrieval refers to the problem of recovering a structured $n$ -dimensional complex-valued vector from its phase-less under-determined linear measurements. The non-linearity of the measurement process makes designing theoretically-analyzable efficient phase retrieval algorithms challenging. As a result, to a great extent, existing recovery algorithms only take advantage of simple structures such as sparsity and its convex generalizations. The goal of this article is to move beyond simple models through employing compression codes. Such codes are typically developed to take advantage of complex signal models to represent the signals as efficiently as possible. In this work, it is shown how an existing compression code can be treated as a black box and integrated into an efficient solution for phase retrieval. First, COmpressive PhasE Retrieval (COPER) optimization, a computationally-intensive compression-based phase retrieval method, is proposed. COPER provides a theoretical framework for studying compression-based phase retrieval. The number of measurements required by COPER is connected to $\kappa $ , the $\alpha $ -dimension (closely related to the rate-distortion dimension) of a given family of compression codes. To finds the solution of COPER, an efficient iterative algorithm called gradient descent for COPER (GD-COPER) is proposed. It is proven that under some mild conditions on the initialization and the compression code, if the number of measurements is larger than $ C \kappa ^{2} \log ^{2}~n$ , where $C$ is a constant, GD-COPER obtains an accurate estimate of the input vector in polynomial time. In the simulation results, JPEG2000 is integrated in GD-COPER to confirm the state-of-the-art performance of the resulting algorithm on real-world images. [ABSTRACT FROM AUTHOR]

We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall Age of Information (AoI). We call this problem the Min-AoI problem. Several special cases of the problem are known to be solvable in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant ${r} \geq 1$ , every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-AoI problem. Second, we give a randomized 2.619-approximation algorithm, a randomized 3-approximation algorithm, which outperforms the previous one in certain scenarios, and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-AoI problem is NP-hard. [ABSTRACT FROM AUTHOR]

In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately $k$ -sparse vector $x \in \mathbb {C} ^{n}$ given access to $y= |\Phi x|$ , where $|v|$ denotes the vector obtained from taking the absolute value of $v\in \mathbb {C} ^{n}$ coordinate-wise. In this paper we present sublinear-time algorithms for a few for-each variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a powerful technique based on Leave-One-Out analysis to the study of low-rank matrix completion problems. Using this technique, we develop a general approach for obtaining fine-grained, entrywise bounds for iterative stochastic procedures in the presence of probabilistic dependency. We demonstrate the power of this approach in analyzing two of the most important algorithms for matrix completion: (i) the non-convex approach based on Projected Gradient Descent (PGD) for a rank-constrained formulation, also known as the Singular Value Projection algorithm, and (ii) the convex relaxation approach based on nuclear norm minimization (NNM). Using this approach, we establish the first convergence guarantee for the original form of PGD without regularization or sample splitting, and in particular shows that it converges linearly in the infinity norm. For NNM, we use this approach to study a fictitious iterative procedure that arises in the dual analysis. Our results show that NNM recovers an $d$ -by- $d$ rank- $r$ matrix with $\mathcal {O}(\mu r \log (\mu r) d\log d)$ observed entries. This bound has optimal dependence on the matrix dimension and is independent of the condition number. To the best of our knowledge, none of previous sample complexity results for tractable matrix completion algorithms satisfies these two properties simultaneously. [ABSTRACT FROM AUTHOR]

Track-before-detect (TkBD) algorithms have been shown to greatly abate measurement-to-track association (MTA) challenges. These simplifications are aptly relevant for reducing operator workload in deployed sonar systems that require a human “in-the-loop.” In a prior manuscript a case study of a passive bearings-only target motion analysis TkBD algorithm was demonstrated in complex sonar scenarios relevant to advanced fielded sonar systems. In this manuscript, a Cramer-Rao Lower Bound (CRLB) is derived for the algorithm previously developed. The approximations used in developing the CRLB are validated with a real data set. The CRLB itself, as a predictor of state estimation error performance, is validated with single- and multi-contact simulated data scenarios. The prior algorithm and CRLB derived herein is applicable to passive sonar, active sonar, radar, and optical applications through a change of point spread functions and Jacobians. The CRLB derived is simple to implement, requires minimal statistical assumptions, and is applicable to similarly implemented TkBD algorithms. [ABSTRACT FROM AUTHOR]

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than $\eta $ nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results. [ABSTRACT FROM AUTHOR]

We consider the setup of nonparametric blind regression for estimating the entries of a large ${m} \times {n}$ matrix, when provided with a small, random fraction of noisy measurements. We assume that all rows ${u} \in [{m}]$ and columns ${i} \in [{n}]$ of the matrix are associated to latent features ${x}_{\text {row}}({{u}})$ and ${x}_{\text {col}}({{i}})$ respectively, and the $({\it{ u, i}})$ -th entry of the matrix, ${A}({\it{ u, i}})$ is equal to ${f}({x}_{\text {row}}({{u}}), {x}_{\text {col}}({{i}}))$ for a latent function $f$. Given noisy observations of a small, random subset of the matrix entries, our goal is to estimate the unobserved entries of the matrix as well as to “de-noise” the observed entries. As the main result of this work, we introduce a nearest-neighbor-based estimation algorithm, and establish its consistency when the underlying latent function $f$ is Lipschitz, the underlying latent space is a bounded diameter Polish space, and the random fraction of observed entries in the matrix is at least $\max \big ({m}^{-1 + \delta }, {n}^{-1/2 + \delta } \big)$ , for any $\delta > 0$. As an important byproduct, our analysis sheds light into the performance of the classical collaborative filtering algorithm for matrix completion, which has been widely utilized in practice. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides a principled improvement over basic collaborative filtering and is competitive with matrix factorization methods. Our algorithm has a natural extension to the setting of tensor completion via flattening the tensor to matrix. When applied to the setting of image in-painting, which is a 3-order tensor, we find that our approach is competitive with respect to state-of-art tensor completion algorithms across benchmark images. [ABSTRACT FROM AUTHOR]

We study the properties of the Frank–Wolfe algorithm to solve the m-Exact-Sparse reconstruction problem, where a signal $y$ must be expressed as a sparse linear combination of a predefined set of atoms, called dictionary. We prove that when the signal is sparse enough with respect to the coherence of the dictionary, then the iterative process implemented by the Frank–Wolfe algorithm only recruits atoms from the support of the signal, is the smallest set of atoms from the dictionary that allows for a perfect reconstruction of $y$. We also prove that under this same condition, there exists an iteration beyond which the algorithm converges exponentially. [ABSTRACT FROM AUTHOR]

In many different applications, it is important to determine the Hilbert transform of a given function. However, it is generally impossible to calculate it in closed form. Therefore Hilbert transform approximations are used. This paper studies the convergence and divergence behavior of general classes of such approximation methods. These classes are characterized by two very natural axioms and they include basically all known traditional numerical algorithms. The convergence of these methods is investigated on a family of signal spaces of continuous functions with finite energy. These spaces are parametrized by a number which measures the energy concentration in the low frequency components of the signal. It is shown that stable methods only exist on signal spaces with a sufficient energy concentration and this paper gives some explicit examples of convergent methods. On all other spaces in the family of signal spaces, every sampling-based Hilbert transform approximation shows a blowup behavior of its peak value, i.e., on these spaces, every sampling-based Hilbert transform approximation diverges. [ABSTRACT FROM AUTHOR]

We consider a generalized version of the correlation clustering problem, defined as follows. Given a complete graph $G$ whose edges are labeled with + or −, we wish to partition the graph into clusters while trying to avoid errors: + edges between clusters or − edges within clusters. Classically, one seeks to minimize the total number of such errors. We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provides a rounding algorithm which converts “fractional clusterings” into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions. [ABSTRACT FROM PUBLISHER]

The fast Fourier transform is the most efficiently known way to compute the discrete Fourier transform (DFT) of an arbitrary n -length signal, and has a computational complexity of O( n\log n) . If the DFT \vec X of the signal \vec x has only $k$ non-zero coefficients (where k< n$ ), can we do better? We addressed this question and presented a novel fast Fourier aliasing-based sparse transform (FFAST) algorithm that cleverly induces sparse-graph alias codes in the DFT domain, via a Chinese-remainder-theorem-guided sub-sampling operation in the time-domain. The induced sparse-graph alias codes are then exploited to devise a fast and iterative onion-peeling style decoder that computes k$ -sparse DFT of an n$ -length signal using only O( k)$ time-domain samples and O( k\log k)$ computations. In this paper, we generalize the FFAST framework by Pawar and Ramchandran to the noisy setting where the time-domain samples are corrupted by white Gaussian noise. We show that the noise-robust R-FFAST algorithm computes a k noise-corrupted time-domain samples in O( k\log ^{4} n) complexity, i.e., sub-linear sample and time complexity. In Section IX, we provide extensive simulation results validating the empirical performance of the R-FFAST algorithm, e.g., we show that the R-FFAST algorithm computes a 50-sparse DFT of an ≈ 10 million length signal using only 4800 noisy samples with an effective signal-to-noise ratio of 5 dB. We also provide comparison of the run-time performance of several existing sparse Fourier transform implementations with that of the R-FFAST and show that it is almost 20 times faster, for comparable settings, than the state-of-the-art algorithm, while simultaneously providing better support recovery guarantees. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results, which demonstrate that the R-FFAST algorithm performs well even for signals like magnetic resonance images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients. [ABSTRACT FROM PUBLISHER]

This semi-tutorial paper introduces the partial-inverse problem for polynomials and develops its application to decoding Reed–Solomon codes and some related codes. The most natural algorithm to solve the partial-inverse problem is very similar to, but more general than, the Berlekamp–Massey algorithm. Two additional algorithms are obtained as easy variations of the basic algorithm: the first variation is entirely new, while the second variation may be viewed as a version of the Euclidean algorithm. Decoding Reed–Solomon codes (and some related codes) can be reduced to the partial-inverse problem, both via the standard key equation and, more naturally, via an alternative key equation with a new converse. Shortened and singly-extended Reed–Solomon codes are automatically included. Using the properties of the partial-inverse problem, two further key equations with attractive properties are obtained. The paper also points out a variety of options for interpolation. [ABSTRACT FROM PUBLISHER]

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]

Several convex formulation methods have been proposed previously for statistical estimation with structured sparsity as the prior. These methods often require a carefully tuned regularization parameter, often a cumbersome or heuristic exercise. Furthermore, the estimate that these methods produce might not belong to the desired sparsity model, albeit accurately approximating the true parameter. Therefore, greedy-type algorithms could often be more desirable in estimating structured-sparse parameters. So far, these greedy methods have mostly focused on linear statistical models. In this paper, we study the projected gradient descent with a non-convex structured-sparse parameter model as the constraint set. Should the cost function have a stable model-restricted Hessian, the algorithm produces an approximation for the desired minimizer. As an example, we elaborate on application of the main results to estimation in generalized linear models. [ABSTRACT FROM AUTHOR]

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]

Random projection has been widely used in data classification. It maps high-dimensional data into a low-dimensional subspace in order to reduce the computational cost in solving the related optimization problem. While previous studies are focused on analyzing the classification performance in the low-dimensional space, in this paper, we consider the recovery problem, i.e., how to accurately recover the optimal solution to the original high-dimensional optimization problem based on the solution learned after random projection. We present a simple algorithm, termed dual random projection, which uses the dual solution of the low-dimensional optimization problem to recover the optimal solution to the original problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution to the original problem, provided that the data matrix is (approximately) low-rank and/or optimal solution is (approximately) sparse. We further show that the proposed algorithm can be applied iteratively to reducing the recovery error exponentially. [ABSTRACT FROM PUBLISHER]

Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy this property with optimal parameters are mainly obtained via probabilistic arguments. Deciding whether a given matrix satisfies the restricted isometry property is a nontrivial computational problem. Indeed, it is shown in this paper that restricted isometry parameters cannot be approximated in polynomial time within any constant factor under the assumption that the hidden clique problem is hard. In addition, on the positive side, an improvement on the brute-force enumeration algorithm for checking the restricted isometry property is proposed. [ABSTRACT FROM PUBLISHER]

The nascent field of compressed sensing is founded on the fact that high-dimensional signals with simple structure can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered. What are the general abstract meanings of structure and simplicity? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor. Minimum complexity pursuit (MCP) requires approximately 2\kappa randomized samples to recover a signal of complexity \kappa and ambient dimension n. We also discuss the performance of the MCP in the presence of measurement noise and with approximately simple signals. [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]

A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with the code length. Thus, the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which “sandwich” the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed \varepsilon > 0 and all sufficiently large code lengths n, polar codes whose rate is within \varepsilon of channel capacity can be constructed in time and space that are both linear in n. [ABSTRACT FROM AUTHOR]

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]

Compressed sensing posits that, within limits, one can undersample a sparse signal and yet reconstruct it accurately. Knowing the precise limits to such undersampling is important both for theory and practice. We present a formula that characterizes the allowed undersampling of generalized sparse objects. The formula applies to approximate message passing (AMP) algorithms for compressed sensing, which are here generalized to employ denoising operators besides the traditional scalar soft thresholding denoiser. This paper gives several examples including scalar denoisers not derived from convex penalization—the firm shrinkage nonlinearity and the minimax nonlinearity—and also nonscalar denoisers—block thresholding, monotone regression, and total variation minimization. Let the variables \varepsilon = k/N and \delta = n/N denote the generalized sparsity and undersampling fractions for sampling the k-generalized-sparse N-vector x0 according to y=Ax0. Here, A is an n\times N measurement matrix whose entries are iid standard Gaussian. The formula states that the phase transition curve \delta = \delta (\varepsilon ) separating successful from unsuccessful reconstruction of x0 by AMP is given by \delta = M(\varepsilon \vert Denoiser) where M(\varepsilon \vert Denoiser) denotes the per-coordinate minimax mean squared error (MSE) of the specified, optimally tuned denoiser in the directly observed problem y = x + z. In short, the phase transition of a noiseless undersampling problem is identical to the minimax MSE in a denoising problem. We prove that this formula follows from state evolution and present numerical results validating it in a wide range of settings. The above formula generates numerous new insights, both in the scalar and in the nonscalar cases. [ABSTRACT FROM PUBLISHER]

The closest vector problem (CVP) and shortest (nonzero) vector problem (SVP) are the core algorithmic problems on Euclidean lattices. They are central to the applications of lattices in many problems of communications and cryptography. Kannan's embedding technique is a powerful technique for solving the approximate CVP; yet, its remarkable practical performance is not well understood. In this paper, the embedding technique is analyzed from a bounded distance decoding (BDD) viewpoint. We present two complementary analyses of the embedding technique: we establish a reduction from BDD to Hermite SVP (via unique SVP), which can be used along with any Hermite SVP solver (including, among others, the Lenstra, Lenstra and Lovász (LLL) algorithm), and show that, in the special case of LLL, it performs at least as well as Babai's nearest plane algorithm (LLL-aided successive interference cancellation). The former analysis helps us to explain the folklore practical observation that unique SVP is easier than standard approximate SVP. It is proven that when the LLL algorithm is employed, the embedding technique can solve the CVP provided that the noise norm is smaller than a decoding radius \lambda1/(2\gamma), where \lambda1 is the minimum distance of the lattice, and \gamma\approx O(2^n/4). This substantially improves the previously best known correct decoding bound \gamma\approxO(2^n). Focusing on the applications of BDD to decoding of multiple-input multiple-output systems, we also prove that BDD of the regularized lattice is optimal in terms of the diversity–multiplexing gain tradeoff, and propose practical variants of embedding decoding which require no knowledge of the minimum distance of the lattice and/or further improve the error performance. [ABSTRACT FROM PUBLISHER]

Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear submanifold of a high-dimensional ambient space. We introduce successive projections onto incoherent manifolds (SPIN), a first-order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current recovery models and algorithms for low-dimensional linear inverse problems and matches (or exceeds) the current state of the art in terms of performance. [ABSTRACT FROM AUTHOR]

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq RTIME(2^polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq DTIME(2^polylog(n)). As the main technical contribution, for any constant 2/3 < \rho < 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code \cal C of length poly(s) with an explicit Hamming ball of radius \rho d(\cal C), such that the projection at the first s coordinates sends the codewords in the ball surjectively onto a linear subspace of dimension s, where d(\cal C) denotes the minimum distance of \cal C. The codes are obtained by concatenating Reed–Solomon codes with Hadamard codes. [ABSTRACT FROM PUBLISHER]

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]

The general theory of greedy approximation is well developed. Much less is known about how specific features of a dictionary can be used to our advantage. In this paper, we discuss incoherent dictionaries. We build a new greedy algorithm which is called the orthogonal super greedy algorithm (OSGA). We show that the rates of convergence of OSGA and the orthogonal matching pursuit (OMP) with respect to incoherent dictionaries are the same. Based on the analysis of the number of orthogonal projections and the number of iterations, we observed that OSGA(s) is s times simpler (more efficient) than OMP. Greedy approximation is also a fundamental tool for sparse signal recovery. The performance of orthogonal multimatching pursuit, a counterpart of OSGA in the compressed sensing setting, is also analyzed under restricted isometry property conditions. [ABSTRACT FROM AUTHOR]

We derive generalization error (loss) bounds for orthogonal matching pursuit algorithms, starting with kernel matching pursuit and sparse kernel principal components analysis. We propose (to the best of our knowledge) the first loss bound for kernel matching pursuit using a novel application of sample compression and Vapnik-Chervonenkis bounds. For sparse kernel principal components analysis, we find that it can be bounded using a standard sample compression analysis, as the subspace it constructs is a compression scheme. We demonstrate empirically that this bound is tighter than previous state-of-the-art bounds for principal components analysis, which use global and local Rademacher complexities. From this analysis we propose a novel sparse variant of kernel canonical correlation analysis and bound its generalization performance using the results developed in this paper. We conclude with a general technique for designing matching pursuit algorithms for other learning domains. [ABSTRACT FROM PUBLISHER]

In this paper, we study the problem of sampling and reconstructing signals which are assumed to lie on or close to one of several subspaces of a Hilbert space. Importantly, we here consider a very general setting in which we allow infinitely many subspaces in infinite dimensional Hilbert spaces. This general approach allows us to unify many results derived recently in areas such as compressed sensing, affine rank minimization, analog compressed sensing and structured matrix decompositions. [ABSTRACT FROM AUTHOR]

“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]

Turbo codes and the iterative algorithm for decoding them sparked a new era in the theory and practice of error control codes. Turbo equalization followed as a natural extension to this development, as an iterative technique for detection and decoding of data that has been both protected with forward error correction and transmitted over a channel with intersymbol interference (ISI). In this paper, we review the turbo equalization approach to coded data transmission over ISI channels, with an emphasis on the basic ideas, some of the practical details, and many of the research directions that have arisen from this offshoot, introduced by Douillard, of the original turbo decoding algorithm. The subsequent relaxation of the maximum a posteriori (MAP) equalization algorithm to include linear and other simpler receivers sparked a decade and a half of research into iterative algorithms, spanning research problems ranging from trellis coded modulation to underwater acoustic communications. [ABSTRACT FROM AUTHOR]

A system with an n-dimensional state vector and a controller and an actor is considered. The controller has complete information about the system state, and reveals a certain “minimum” amount of information to the actor. The actor takes certain actions based on the information the controller reveals, and the actions fetch certain utilities for each entity. Both the controller and actor seek to maximize their individual utilities by respectively selecting the information to reveal and the actions to adopt. This decision problem forms the basis of several technical and social systems, and can be formulated as a signaling game. It is shown that the Perfect Bayesian Equilibrium of this game has several counterintuitive properties and can be obtained as a saddle point of a different two person zero sum game. The computation time for saddle points using standard linear programs however turns out to be superexponential in n, which leads to computational intractability even for moderate n. Algorithms for computing saddle point policies using a computation time that is exponential in n are presented. Finally, simple linear time computable policies that approximate the saddle-point policies within guaranteeable approximation ratios are obtained. [ABSTRACT FROM PUBLISHER]