Search

Orthogonal/vector approximate message-passing (AMP) is a powerful message-passing (MP) algorithm for signal reconstruction in compressed sensing. This paper proves the convergence of Bayes-optimal orthogonal/vector AMP in the large system limit. The proof strategy is based on a novel long-memory (LM) MP approach: A first step is a construction of LM-MP that is guaranteed to converge systematically. A second step is a large-system analysis of LM-MP via an existing framework of state evolution. A third step is to prove the convergence of state evolution recursions for Bayes-optimal LM-MP via a new statistical interpretation of existing LM damping. The last is an exact reduction of the state evolution recursions for Bayes-optimal LM-MP to those for Bayes-optimal orthogonal/vector AMP. The convergence of the state evolution recursions for Bayes-optimal LM-MP implies that for Bayes-optimal orthogonal/vector AMP. Numerical simulations are presented to show the verification of state evolution results for damped orthogonal/vector AMP and a negative aspect of LM-MP in finite-sized systems. [ABSTRACT FROM AUTHOR]

In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. Under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing, our results may be of interest for researchers working in areas as diverse as linear sketching, coding theory, matrix compression and dictionary learning. [ABSTRACT FROM AUTHOR]

We describe in detail the interplay between binary symplectic geometry and notions from quantum computation, with the ultimate goal of constructing highly structured codebooks. The Binary Chirps (BCs) are Complex Grassmannian Lines in $N = 2^{m}$ dimensions used in deterministic compressed sensing and random/unsourced multiple access in wireless networks. Their entries are fourth roots of unity and can be described in terms of second order Reed-Muller codes. The Binary Subspace Chirps (BSSCs) are a unique collection of BCs of ranks ranging from $r=0$ to $r = m$ , embedded in $N$ dimensions according to an on-off pattern determined by a rank $r$ binary subspace. This yields a codebook that is asymptotically 2.38 times larger than the codebook of BCs, has the same minimum chordal distance as the codebook of BCs, and the alphabet is minimally extended from $\{\pm 1,\pm i\}$ to $\{\pm 1,\pm i, 0\}$. Equivalently, we show that BSSCs are stabilizer states, and we characterize them as columns of a well-controlled collection of Clifford matrices. By construction, the BSSCs inherit all the properties of BCs, which in turn makes them good candidates for a variety of applications. For applications in wireless communication, we use the rich algebraic structure of BSSCs to construct a low complexity decoding algorithm that is reliable against Gaussian noise. In simulations, BSSCs exhibit an error probability comparable or slightly lower than BCs, both for single-user and multi-user transmissions. [ABSTRACT FROM AUTHOR]

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable (e.g., perform poorly or even diverge) for other matrix ensembles, especially for ill-conditioned ones. To solve this issue, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP (BO-OAMP/VAMP) requires a high-complexity linear minimum mean square error (MMSE) estimator. This prevents OAMP/VAMP from being used in large-scale systems. To address the drawbacks of AMP and BO-OAMP/VAMP, this paper offers a memory AMP (MAMP) framework based on the orthogonality principle, which ensures that estimation errors in MAMP are asymptotically IID Gaussian. To realize the required orthogonality for MAMP, we provide an orthogonalization procedure for the local memory estimators. In addition, we propose a Bayes-optimal MAMP (BO-MAMP), in which a long-memory matched filter is used for interference suppression. The complexity of BO-MAMP is comparable to AMP. To asymptotically characterize the performance of BO-MAMP, a state evolution is derived. The relaxation parameters and damping vector in BO-MAMP are optimized based on state evolution. Most crucially, the state evolution of the optimized BO-MAMP converges to the same fixed point as that of the high-complexity BO-OAMP/VAMP for all right-unitarily-invariant matrices, and achieves the Bayes optimal MSE predicted by the replica method if its state evolution has a unique fixed point. Finally, simulations are provided to verify the theoretical results’ validity and accuracy. [ABSTRACT FROM AUTHOR]

Consider the compressed sensing setup where the support $\mathbf {s}^{\ast}$ of an $m$ -sparse $d$ -dimensional signal $\mathbf {x}$ is to be recovered from $n$ linear measurements with a given algorithm. Suppose that the measurements are such that the algorithm does not guarantee perfect support recovery and that true features may be missed. Can they efficiently be retrieved? We address this question through a simple error-correction module referred to as LiRE. LiRE takes as input an estimate $\mathbf {s}_{\text {in}}$ of the true support $\mathbf {s}^{\ast}$ , and outputs a refined support estimate $\mathbf {s}_{\text {out}}$. We establish sufficient conditions under which LiRE is guaranteed to recover the entire support, that is $\mathbf {s}_{\text {out}}\supseteq \mathbf {s}^{\ast} $. These conditions imply, for instance, that in high dimension LiRE can correct a sublinear in $m$ number of errors made by Orthogonal Matching Pursuit (OMP). The computational complexity of LiRE is ${\mathcal{O}}(m n d)$. Experimental results with random Gaussian design matrices show that LiRE substantially reduces the number of measurements needed for perfect support recovery via Compressive Sampling Matching Pursuit, Basis Pursuit (BP), and OMP. Interestingly, adding LiRE to OMP yields a support recovery procedure that is more accurate and significantly faster than BP. This observation carries over in the noisy measurement setup where the combination of LiRE and OMP is faster and more accurate than LASSO. Finally, as a standalone support recovery algorithm with a random initialization, experiments show that LiRE’s support recovery performance lies between OMP and BP. These results show that LiRE can be used generically, on top of any suboptimal baseline support recovery algorithm, to improve support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead. Alternatively, LiRE may be used as a standalone support recovery algorithm that is competitive with respect to OMP. [ABSTRACT FROM AUTHOR]

Conventional sparse phase retrieval schemes can recover sparse signals from the magnitude of linear measurements only up to a global phase ambiguity. This work proposes a novel approach that instead utilizes the magnitude of affine measurements to achieve ambiguity-free signal reconstruction. The proposed method relies on two-stage approach that consists of support identification followed by the exact recovery of nonzero signal entries. In the noise-free case, perfect support identification using a simple counting rule is guaranteed subject to a mild condition on the signal sparsity, and subsequent exact recovery of the nonzero signal entries can be obtained in closed-form. The proposed approach is then extended to two noisy scenarios, namely, sparse noise (or outliers) and non-sparse bounded noise. For both cases, perfect support identification is still ensured under mild conditions on the noise model, namely, the support size for sparse outliers and the power of the bounded noise. Under perfect support identification, exact signal recovery can be achieved using a simple majority rule for the sparse noise scenario, and reconstruction up to a bounded error can be achieved using linear least-squares (LS) estimation for the non-sparse bounded noise scenario. The obtained analytic performance guarantee for the latter case also sheds light on the construction of the sensing matrix and bias vector. In fact, we show that a near optimal performance can be achieved with high probability by the random generation of the nonzero entries of the sparse sensing matrix and bias vector according to the uniform distribution over a circle. Computer simulations using both synthetic and real-world data sets are provided to demonstrate the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

Deep generative models have emerged as a powerful class of priors for signals in various inverse problems such as compressed sensing, phase retrieval and super-resolution. In this work, we consider the compressed sensing problem and assume the unknown signal to lie in the range of some pre-trained generative model. A popular approach for signal recovery is via gradient descent in the low-dimensional latent space. While gradient descent has achieved good empirical performance, its theoretical behavior is not well understood. We introduce the use of stochastic gradient Langevin dynamics (SGLD) for compressed sensing with a generative prior. Under mild assumptions on the generative model, we prove the convergence of SGLD to the true signal. We also demonstrate competitive empirical performance to standard gradient descent. [ABSTRACT FROM AUTHOR]

Speckle or multiplicative noise is a critical issue in coherence-based imaging systems, such as synthetic aperture radar and optical coherence tomography. Existence of speckle noise considerably limits the applicability of such systems by degrading their performance. On the other hand, the sophistications that arise in the study of multiplicative noise have so far impeded theoretical analysis of such imaging systems. As a result, the current acquisition technology relies on heuristic solutions, such as oversampling the signal and converting the problem into a denoising problem with multiplicative noise. This paper attempts to bridge the gap between theory and practice by providing the first theoretical analysis of such systems. To achieve this goal the log-likelihood function corresponding to measurement systems with speckle noise is characterized. Then employing compression codes to model the source structure, for the case of under-sampled measurements, a compression-based maximum likelihood recovery method is proposed. The mean squared error (MSE) performance of the proposed method is characterized and is shown to scale as $O\left({\sqrt {\frac{k \log n }{ m}}}\right)$ , where $k$ , $m$ and $n$ denote the intrinsic dimension of the signal class according to the compression code, the number of observations, and the ambient dimension of the signal, respectively. This result, while in contrast to imaging systems with additive noise in which MSE scales as $O\left({{\frac{k \log n }{ m}}}\right)$ , suggests that if the signal class is structured (i.e., $k \ll n$), accurate recovery of a signal from under-determined measurements is still feasible, even in the presence of speckle noise. Simulation results are presented that suggest image recovery under multiplicative noise is inherently more challenging than additive noise, and that the derived theoretical results are sharp. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the generalization performance of the Iterative Hard Thresholding (IHT) algorithm widely used for sparse recovery problems. The parameter estimation and sparsity recovery consistency of IHT has long been known in compressed sensing. From the perspective of statistical learning, another fundamental question is how well the IHT estimation would predict on unseen data. This paper makes progress towards answering this open question by introducing a novel sparse generalization theory for IHT under the notion of algorithmic stability. Our theory reveals that: 1) under natural conditions on the empirical risk function over $n$ samples of dimension $p$ , IHT with sparsity level $k$ enjoys an $\tilde {\mathcal {O}}(n^{-1/2}\sqrt {k\log (n)\log (p)})$ rate of convergence in sparse excess risk; 2) a tighter $\tilde {\mathcal {O}}(n^{-1/2}\sqrt {\log (n)})$ bound can be established by imposing an additional iteration stability condition on a hypothetical IHT procedure invoked to the population risk; and 3) a fast rate of order $\tilde {\mathcal {O}}\left ({n^{-1}k(\log ^{3}(n)+\log (p))}\right)$ can be derived for strongly convex risk function under proper strong-signal conditions. The results have been substantialized to sparse linear regression and sparse logistic regression models to demonstrate the applicability of our theory. Preliminary numerical evidence is provided to support our theoretical predictions. [ABSTRACT FROM AUTHOR]

This paper is concerned with the problem of recovering a structured signal from a relatively small number of corrupted random measurements. Sharp phase transitions have been numerically observed in practice when different convex programming procedures are used to solve this problem. This paper is devoted to presenting theoretical explanations for these phenomena by employing some basic tools from Gaussian process theory. Specifically, we identify the precise locations of the phase transitions for both constrained and penalized recovery procedures. Our theoretical results show that these phase transitions are determined by some geometric measures of structure, e.g., the spherical Gaussian width of a tangent cone and the Gaussian (squared) distance to a scaled subdifferential. By utilizing the established phase transition theory, we further investigate the relationship between these two kinds of recovery procedures, which also reveals an optimal strategy (in the sense of Lagrange theory) for choosing the tradeoff parameter in the penalized recovery procedure. Numerical experiments are provided to verify our theoretical results. [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]

Recently, Liu and Zhang studied the rather challenging problem of time series forecasting from the perspective of compressed sensing. They proposed a no-learning method, named Convolution Nuclear Norm Minimization (CNNM), and proved that CNNM can exactly recover the future part of a series from its observed part, provided that the series is convolutionally low-rank. While impressive, the convolutional low-rankness condition may not be satisfied whenever the series is far from being seasonal, and is in fact brittle to the presence of trends and dynamics. This paper tries to approach the issues by integrating a learnable, orthonormal transformation into CNNM, with the purpose for converting the series of involute structures into regular signals of convolutionally low-rank. We prove that the resultant model, termed Learning-Based CNNM (LbCNNM), strictly succeeds in identifying the future part of a series, as long as the transform of the series is convolutionally low-rank. To learn proper transformations that may meet the required success conditions, we devise an interpretable method based on Principal Component Pursuit (PCP). Equipped with this learning method and some elaborate data argumentation skills, LbCNNM not only can handle well the major components of time series (including trends, seasonality and dynamics), but also can make use of the forecasts provided by some other forecasting methods; this means LbCNNM can be used as a general tool for model combination. Extensive experiments on 100,452 real-world time series from Time Series Data Library (TSDL) and M4 Competition (M4) demonstrate the superior performance of LbCNNM. [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]

We study the problem of signal estimation from non-linear observations whenthe signal belongs to a low-dimensional set buried in a high-dimensional space.A rough heuristic often used in practice postulates that non-linearobservations may be treated as noisy linear observations, and thus the signalmay be estimated using the generalized Lasso. This is appealing because of theabundance of efficient, specialized solvers for this program. Just as noise maybe diminished by projecting onto the lower dimensional space, the error frommodeling non-linear observations with linear observations will be greatlyreduced when using the signal structure in the reconstruction. We allow generalsignal structure, only assuming that the signal belongs to some set K in R^n.We consider the single-index model of non-linearity. Our theory allows thenon-linearity to be discontinuous, not one-to-one and even unknown. We assume arandom Gaussian model for the measurement matrix, but allow the rows to have anunknown covariance matrix. As special cases of our results, we recovernear-optimal theory for noisy linear observations, and also give the firsttheoretical accuracy guarantee for 1-bit compressed sensing with unknowncovariance matrix of the measurement vectors.

Many applications have benefited remarkably from low-dimensional models inthe recent decade. The fact that many signals, though high dimensional, areintrinsically low dimensional has given the possibility to recover them stablyfrom a relatively small number of their measurements. For example, incompressed sensing with the standard (synthesis) sparsity prior and in matrixcompletion, the number of measurements needed is proportional (up to alogarithmic factor) to the signal's manifold dimension. Recently, a new natural low-dimensional signal model has been proposed: thecosparse analysis prior. In the noiseless case, it is possible to recoversignals from this model, using a combinatorial search, from a number ofmeasurements proportional to the signal's manifold dimension. However, if weask for stability to noise or an efficient (polynomial complexity) solver, allthe existing results demand a number of measurements which is far removed fromthe manifold dimension, sometimes far greater. Thus, it is natural to askwhether this gap is a deficiency of the theory and the solvers, or if thereexists a real barrier in recovering the cosparse signals by relying only ontheir manifold dimension. Is there an algorithm which, in the presence ofnoise, can accurately recover a cosparse signal from a number of measurementsproportional to the manifold dimension? In this work, we prove that there is nosuch algorithm. Further, we show through numerical simulations that even in thenoiseless case convex relaxations fail when the number of measurements iscomparable to the manifold dimension. This gives a practical counter-example tothe growing literature on compressed acquisition of signals based on manifolddimension.

Data samples from ${\mathbb{R}}^ {d}$ with a common support of size $k$ are accessed through $m$ random linear projections (measurements) per sample. It is well-known that roughly $k$ measurements from a single sample are sufficient to recover the support. In the multiple sample setting, do $k$ overall measurements still suffice when only $m$ measurements per sample are allowed, with $m < k$ ? We answer this question in the negative by considering a generative model setting with independent samples drawn from a subgaussian prior. We show that $n=\Theta ((k^{2}/ m^{2})\cdot \log k(d- k))$ samples are necessary and sufficient to recover the support exactly. In turn, this shows that when $m < k$ , $k$ overall measurements are insufficient for support recovery; instead we need about $m$ measurements each from $k^{2}/ m^{2}$ samples, and therefore $k^{2}/ m$ overall measurements are necessary. [ABSTRACT FROM AUTHOR]

In compressed sensing, the restricted isometry property (RIP) on $M \times N$ sensing matrices (where $M < N$) guarantees efficient reconstruction of sparse vectors. A matrix has the $(s,\delta)$ - $\mathsf {RIP}$ property if behaves as a $\delta $ -approximate isometry on $s$ -sparse vectors. It is well known that an $M\times N$ matrix with i.i.d. $\mathcal {N}(0,1/M)$ entries is $(s,\delta)$ - $\mathsf {RIP}$ with high probability as long as $s\lesssim \delta ^{2}~M/\log N$. On the other hand, most prior works aiming to deterministically construct $(s,\delta)$ - $\mathsf {RIP}$ matrices have failed when $s \gg \sqrt {M}$. An alternative way to find an RIP matrix could be to draw a random gaussian matrix and certify that it is indeed RIP. However, there is evidence that this certification task is computationally hard when $s \gg \sqrt {M}$ , both in the worst case and the average case. In this paper, we investigate the exact average-case time complexity of certifying the RIP property for $M\times N$ matrices with i.i.d. $\mathcal {N}(0,1/M)$ entries, in the “possible but hard” regime $\sqrt {M} \ll s\lesssim M/\log N$. Based on analysis of the low-degree likelihood ratio, we give rigorous evidence that subexponential runtime $N^{\tilde \Omega (s^{2}/M)}$ is required, demonstrating a smooth tradeoff between the maximum tolerated sparsity and the required computational power. This lower bound is essentially tight, matching the runtime of an existing algorithm due to Koiran and Zouzias. Our hardness result allows $\delta $ to take any constant value in (0, 1), which captures the relevant regime for compressed sensing. This improves upon the existing average-case hardness result of Wang et al., which is limited to $\delta = o(1)$. [ABSTRACT FROM AUTHOR]

Consider a (multiple-access) wireless communication system where users are connected to a unique base station over a shared-spectrum radio links. Each user has a fixed number k of bits to send to the base station, and his signal gets attenuated by a random channel gain (quasi-static fading). In this paper we consider the many-user asymptotics of Chen-Chen-Guo’2017, where the number of users grows linearly with the blocklength. Differently, though, we adopt a per-user probability of error (PUPE) criterion (as opposed to classical joint-error probability criterion). Under PUPE the finite energy-per-bit communication is possible, and we are able to derive bounds on the tradeoff between energy and spectral efficiencies. We reconfirm the curious behaviour (previously observed for non-fading MAC) of the possibility of almost perfect multi-user interference (MUI) cancellation for user densities below a critical threshold. Further, we demonstrate the suboptimality of standard solutions such as orthogonalization (i.e. TDMA/FDMA) and treating interference as noise (i.e. pseudo-random CDMA without multi-user detection). Notably, the problem treated here can be seen as a variant of support recovery in compressed sensing for the unusual definition of sparsity with one non-zero entry per each contiguous section of 2k coordinates. This identifies our problem with that of the sparse regression codes (SPARCs) and hence our results can be equivalently understood in the context of SPARCs with sections of length 2100. Finally, we discuss the relation of the almost perfect MUI cancellation property and the replica-method predictions. [ABSTRACT FROM AUTHOR]

Compressed sensing is an emerging theory of signal processing and it has wide applications in many frontier fields. The construction of the measurement matrices is still a central problem in compressed sensing. In this paper, two types of deterministic constructions of binary measurement matrices are presented via unitary geometry. Then, the lower bounds of the spark of unitary geometry measurement matrices are theoretically analyzed, and an asymptotic comparison between unitary geometry measurement matrices and projective geometry measurement matrices is given via the worst-case recovery capability. After that, a clipping-embedding operation is proposed for binary matrices to generate measurement matrices with more sizes, which can strongly extend the applicability of the deterministic binary matrices in practice. Finally, simulation results demonstrate that the performance of our measurement matrices is comparable to, sometimes even better than, that of the corresponding Gaussian random matrices under OMP and BP. [ABSTRACT FROM AUTHOR]

This paper studies a generalization of sparse superposition codes (SPARCs) for communication over the complex additive white Gaussian noise (AWGN) channel. In a SPARC, the codebook is defined in terms of a design matrix, and each codeword is a generated by multiplying the design matrix with a sparse message vector. In the standard SPARC construction, information is encoded in the locations of the non-zero entries of the message vector. In this paper we generalize the construction and consider modulated SPARCs, where information is encoded in both the locations and the values of the non-zero entries of the message vector. We focus on the case where the non-zero entries take values from a phase-shift keying (PSK) constellation. We propose a computationally efficient approximate message passing (AMP) decoder, and obtain analytical bounds on the state evolution parameters which predict the error performance of the decoder. Using these bounds we show that PSK-modulated SPARCs are asymptotically capacity achieving for the complex AWGN channel, with either spatial coupling or power allocation. We also provide numerical simulation results to demonstrate the error performance at finite code lengths. These results show that introducing modulation to the SPARC design can significantly reduce decoding complexity without sacrificing error performance. [ABSTRACT FROM AUTHOR]

Sparse superposition codes, also referred to as sparse regression codes (SPARCs), are a class of codes for efficient communication over the AWGN channel at rates approaching the channel capacity. In a standard SPARC, codewords are sparse linear combinations of columns of an i.i.d. Gaussian design matrix, while in a spatially coupled SPARC the design matrix has a block-wise structure, where the variance of the Gaussian entries can be varied across blocks. A well-designed spatial coupling structure can significantly enhance the error performance of iterative decoding algorithms such as Approximate Message Passing (AMP). In this paper, we obtain a non-asymptotic bound on the probability of error of spatially coupled SPARCs with AMP decoding. Applying this bound to a simple band-diagonal design matrix, we prove that spatially coupled SPARCs with AMP decoding achieve the capacity of the AWGN channel. The bound also highlights how the decay of error probability depends on each design parameter of the spatially coupled SPARC. An attractive feature of AMP decoding is that its asymptotic mean squared error (MSE) can be predicted via a deterministic recursion called state evolution. Our result provides the first proof that the MSE concentrates on the state evolution prediction for spatially coupled designs. Combined with the state evolution prediction, this result implies that spatially coupled SPARCs with the proposed band-diagonal design are capacity-achieving. Using the proof technique used to establish the main result, we also obtain a concentration inequality for the MSE of AMP applied to compressed sensing with spatially coupled design matrices. Finally, we provide numerical simulation results that demonstrate the finite length error performance of spatially coupled SPARCs. The performance is compared with coded modulation schemes that use LDPC codes from the DVB-S2 standard. [ABSTRACT FROM AUTHOR]

This paper proposes Bayes-optimal convolutional approximate message-passing (CAMP) for signal recovery in compressed sensing. CAMP uses the same low-complexity matched filter (MF) for interference suppression as approximate message-passing (AMP). To improve the convergence property of AMP for ill-conditioned sensing matrices, the so-called Onsager correction term in AMP is replaced by a convolution of all preceding messages. The tap coefficients in the convolution are determined so as to realize asymptotic Gaussianity of estimation errors via state evolution (SE) under the assumption of orthogonally invariant sensing matrices. An SE equation is derived to optimize the sequence of denoisers in CAMP. The optimized CAMP is proved to be Bayes-optimal for all orthogonally invariant sensing matrices if the SE equation converges to a fixed-point and if the fixed-point is unique. For sensing matrices with low-to-moderate condition numbers, CAMP can achieve the same performance as high-complexity orthogonal/vector AMP that requires the linear minimum mean-square error (LMMSE) filter instead of the MF. [ABSTRACT FROM AUTHOR]

We consider the question of estimating a real low-complexity signal (such as a sparse vector or a low-rank matrix) from the phase of complex random measurements. We show that in this phase-only compressive sensing (PO-CS) scenario, we can perfectly recover such a signal with high probability and up to global unknown amplitude if the sensing matrix is a complex Gaussian random matrix and the number of measurements is large compared to the complexity level of the signal space. Our approach proceeds by recasting the (non-linear) PO-CS scheme as a linear compressive sensing model built from a signal normalization constraint, and a phase-consistency constraint imposing any signal estimate to match the observed phases in the measurement domain. Practically, stable and robust estimation of the signal direction is achieved from any instance optimal algorithm of the compressive sensing literature (such as basis pursuit denoising). This is ensured by proving that the matrix associated with this equivalent linear model satisfies with high probability the restricted isometry property under the above condition on the number of measurements. We finally observe experimentally that robust signal direction recovery is reached at about twice the number of measurements needed for signal recovery in compressive sensing. [ABSTRACT FROM AUTHOR]

This work is concerned with the problem of recovering high-dimensional signals x ∈ Rn which belong to a convex set of low complexity from a small number of quantized measurements. We propose to estimate the signals via a convex program based on rectified linear units (ReLUs) for two different quantization schemes, namely one-bit and uniform multi-bit quantization. Assuming that the linear measurement process can be modelled by a sensing matrix with i.i.d. subgaussian rows, we obtain for both schemes near-optimal uniform reconstruction guarantees by adding well-designed noise to the linear measurements prior to the quantization step. In the one-bit case, we show that the program is robust against adversarial bit corruptions as well as additive noise on the linear measurements. Further, our analysis quantifies precisely how the rate-distortion relationship of the program changes depending on whether we seek reconstruction accuracies above or below the level of additive noise. The proofs rely on recent results by Dirksen and Mendelson on non-Gaussian hyperplane tessellations. Finally, we complement our theoretical analysis with numerical experiments which compare our method to other state-of-the-art methodologies. [ABSTRACT FROM AUTHOR]

Much of the existing literature in sparse recovery is concerned with the following question: given a sparsity pattern and a corresponding regularizer, derive conditions on the dictionary under which exact recovery is possible. In this paper, we study the opposite question: given a dictionary and the ℓ1-norm regularizer, find the largest sparsity pattern that can be recovered. We show that such a pattern is described by a mathematical object called a “maximum abstract simplicial complex,” and provide two different characterizations of this object: one based on extreme points and the other based on vectors of minimal support. In addition, we show how this new framework is useful in the study of sparse recovery problems when the dictionary takes the form of a graph incidence matrix or a partial discrete Fourier transform. In case of incidence matrices, we show that the largest sparsity pattern that can be recovered is determined by the set of simple cycles of the graph. As a byproduct, we show that standard sparse recovery can be certified in polynomial time, although this is known to be NP-hard for general matrices. In the case of the partial discrete Fourier transform, our characterization of the largest sparsity pattern that can be recovered requires the unknown signal to be real and its dimension to be a prime number. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of user activity detection and large-scale fading coefficient estimation in a random access wireless uplink with a massive MIMO base station with a large number M of antennas and a large number of wireless single-antenna devices (users). We consider a block fading channel model where the M-dimensional channel vector of each user remains constant over a coherence block containing L signal dimensions in time-frequency. In the considered setting, the number of potential users Ktot is much larger than L but at each time slot only Ka << Ktot of them are active. Previous results, based on compressed sensing, require that Ka ≤ L, which is a bottleneck in massive deployment scenarios. In this work, we show that such limitation can be overcome when the number of base station antennas M is sufficiently large. More specifically, we prove that with a coherence block of dimension L and a number of antennas M such that Ka/M = o(1), one can identify Ka = O(L2/log2 (Ktot/Ka)) active users, which is much larger than the previously known bounds. We also provide two algorithms. One is based on Non-Negative Least-Squares, for which the above scaling result can be rigorously proved. The other consists of a low-complexity iterative componentwise minimization of the likelihood function of the underlying problem. While for this algorithm a rigorous proof cannot be given, we analyze a constrained version of the Maximum Likelihood (ML) problem (a combinatorial optimization with exponential complexity) and find the same fundamental scaling law for the number of identifiable users. Therefore, we conjecture that the low-complexity (approximated) ML algorithm also achieves the same scaling law and we demonstrate its performance by simulation. We also compare the discussed methods with the (Bayesian) MMV-AMP algorithm, recently proposed for the same setting, and show superior performance and better numerical stability. Finally, we use the discussed approximated ML algorithm as the inner decoder in a concatenated coding scheme for unsourced random access, a grant-free uncoordinated multiple access scheme where all users make use of the same codebook, and the receiver must produce the list of transmitted messages, irrespectively of the identity of the transmitters. We show that reliable communication is possible at any Eb/N0 provided that a sufficiently large number of base station antennas is used, and that a sum spectral efficiency in the order of O(L log (L)) is achievable. [ABSTRACT FROM AUTHOR]

We study a class of real robust phase retrieval problems under a Gaussian assumption on the coding matrix when the received signal is sparsely corrupted by noise. The goal is to establish conditions on the sparsity under which the input vector can be exactly recovered. The recovery problem is formulated as residual minimization in the $\ell _{1}$ -norm. The main contribution is a robust phase retrieval counterpart to the seminal paper by Candes and Tao on compressed sensing ($\ell _{1}$ regression) [Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005]. The analysis depends on a key new property of the coding matrix called the Absolute Range Property (ARP) which is the analogue to the Null Space Property (NSP) in compressed sensing. When the residuals are computed using squared magnitudes, we show that ARP follows from a standard Restricted Isometry Property (RIP). However, when the residuals are computed using absolute magnitudes, a different kind of RIP or growth property is required. We conclude by showing that the robust phase retrieval objectives are sharp with respect to their minimizers with high probability. [ABSTRACT FROM AUTHOR]

We investigate the statistical and algorithmic properties of random neural-network generative priors in a simple inference problem: spiked-matrix estimation. We establish a rigorous expression for the performance of the Bayes-optimal estimator in the high-dimensional regime, and identify the statistical threshold for weak-recovery of the spike. Next, we derive a message-passing algorithm taking into account the latent structure of the spike, and show that its performance is asymptotically optimal for natural choices of the generative network architecture. The absence of an algorithmic gap in this case is in stark contrast to known results for sparse spikes, another popular prior for modelling low-dimensional signals, and for which no algorithm is known to achieve the optimal statistical threshold. Finally, we show that linearising our message passing algorithm yields a simple spectral method also achieving the optimal threshold for reconstruction. We conclude with an experiment on a real data set showing that our bespoke spectral method outperforms vanilla PCA. [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]

This article introduces a novel scheme, termed coded compressed sensing, for unsourced multiple-access communication. The proposed divide-and-conquer approach leverages recent advances in compressed sensing and forward error correction to produce a novel uncoordinated access paradigm, along with a computationally efficient decoding algorithm. Within this framework, every active device partitions its data into several sub-blocks and, subsequently, adds redundancy using a systematic linear block code. Compressed sensing techniques are then employed to recover sub-blocks up to a permutation of their order, and the original messages are obtained by stitching fragments together using a tree-based algorithm. The error probability and computational complexity of this access paradigm are characterized. An optimization framework, which exploits the tradeoff between performance and computational complexity, is developed to assign parity-check bits to each sub-block. In addition, two emblematic parity bit allocation strategies are examined and their performances are analyzed in the limit as the number of active users and their corresponding payloads tend to infinity. The number of channel uses needed and the computational complexity associated with these allocation strategies are established for various scaling regimes. Numerical results demonstrate that coded compressed sensing outperforms other existing practical access strategies over a range of operational scenarios. [ABSTRACT FROM AUTHOR]

Extracting information from nonlinear measurements is a fundamental challenge in data analysis. In this work, we consider separable inverse problems, where the data are modeled as a linear combination of functions that depend nonlinearly on certain parameters of interest. These parameters may represent neuronal activity in a human brain, frequencies of electromagnetic waves, fluorescent probes in a cell, or magnetic relaxation times of biological tissues. Separable nonlinear inverse problems can be reformulated as underdetermined sparse-recovery problems, and solved using convex programming. This approach has had empirical success in a variety of domains, from geophysics to medical imaging, but lacks a theoretical justification. In particular, compressed-sensing theory does not apply, because the measurement operators are deterministic and violate incoherence conditions such as the restricted-isometry property. Our main contribution is a theory for sparse recovery adapted to deterministic settings. We show that convex programming succeeds in recovering the parameters of interest, as long as their values are sufficiently distinct with respect to the correlation structure of the measurement operator. The theoretical results are illustrated through numerical experiments for two applications: heat-source localization and estimation of brain activity from electroencephalography data. [ABSTRACT FROM AUTHOR]

The minimum description length (MDL) principle is extended to supervised learning. The MDL principle is a philosophy that the shortest description of given data leads to the best hypothesis about the data source. One of the key theories for the MDL principle is Barron and Cover’s theory (BC theory), which mathematically justifies the MDL principle based on two-stage codes in density estimation (unsupervised learning). Though the codelength of two-stage codes looks similar to the target function of penalized likelihood methods, parameter optimization of penalized likelihood methods is done without quantization of parameter space. Recently, Chatterjee and Barron have provided theoretical tools to extend BC theory to penalized likelihood methods by overcoming this difference. Indeed, applying their tools, they showed that the famous penalized likelihood method ‘lasso’ can be interpreted as an MDL estimator and enjoys performance guarantee by BC theory. An important fact is that their results assume a fixed design setting, which is essentially the same as unsupervised learning. The fixed design is natural if we use lasso for compressed sensing. If we use lasso for supervised learning, however, the fixed design is considerably unsatisfactory. Only random design is acceptable. However, it is inherently difficult to extend BC theory to the random design regardless of whether the parameter space is quantized or not. In this paper, a novel theoretical tool for extending BC theory to supervised learning (the random design setting and no quantization of parameter space) is provided. Applying this tool, when the covariates are subject to a Gaussian distribution, it is proved that lasso in the random design setting can also be interpreted as an MDL estimator, and that lasso enjoys the risk bound of BC theory. The risk/regret bounds obtained have several advantages inherited from BC theory. First, the bounds require remarkably few assumptions. Second, the bounds hold for any finite sample size $n$ and any finite feature number $p$ even if $n\ll p$. Behavior of the regret bound is investigated by numerical simulations. We believe that this is the first extensions of BC theory to supervised learning (random design). [ABSTRACT FROM AUTHOR]

In this paper, we consider the recovery of $k$ -sparse signals using the weighted $\ell _{p}$ ($0< p \leqslant 1$) minimization when some partial prior information on the support is available. First, we present a unified analysis of restricted isometry constant $\delta _{tk}$ with $d< t \leqslant 2d$ ($d \geqslant 1$ is determined by the prior support information) for sparse signal recovery by the weighted $\ell _{p}$ ($0< p \leqslant 1$) minimization in both noiseless and noisy settings. This result fills a vacancy on $\delta _{tk}$ with $t< 2$ , compared with previous works on $\delta _{(a+1)k}$ ($a>1$). Second, we provide a sufficient condition on $\delta _{tk}$ with $1< t \leqslant 2$ for the recovery of sparse signals using the $\ell _{p}$ ($0< p \leqslant 1$) minimization, which extends the existing optimal result on $\delta _{2k}$ in the literature. Last, various numerical examples are presented to demonstrate the better performance of the weighted $\ell _{p}$ ($0< p \leqslant 1$) minimization is achieved when the accuracy of prior information on the support is at least 50%, compared with that of the $\ell _{p}$ ($0< p \leqslant 1$) minimization. [ABSTRACT FROM AUTHOR]

In this work, we perform a complete failure analysis of the interval-passing algorithm (IPA) for compressed sensing. The IPA is an efficient iterative algorithm for reconstructing a $k$ -sparse nonnegative $n$ -dimensional real signal ${x}$ from a small number of linear measurements ${y}$. In particular, we show that the IPA fails to recover ${x}$ from ${y}$ if and only if it fails to recover a corresponding binary vector of the same support, and also that only positions of nonzero values in the measurement matrix are of importance to the success of recovery. Based on this observation, we introduce termatiko sets and show that the IPA fails to fully recover ${x}$ if and only if the support of ${x}$ contains a nonempty termatiko set, thus giving a complete (graph-theoretic) description of the failing sets of the IPA. Two heuristics to locate small-size termatiko sets are presented. For binary column-regular measurement matrices with no 4-cycles, we provide a lower bound on the termatiko distance, defined as the smallest size of a nonempty termatiko set. For measurement matrices constructed from the parity-check matrices of array low-density parity-check codes, upper bounds on the termatiko distance equal to half the best known upper bound on the minimum distance are provided for column-weight at most 7, while for column-weight 3, the exact termatiko distance and its corresponding multiplicity are provided. Next, we show that adding redundant rows to the measurement matrix does not create new termatiko sets, but rather potentially removes termatiko sets and thus improves performance. An algorithm is provided to efficiently search for such redundant rows. Finally, we present numerical results for different specific measurement matrices and also for protograph-based ensembles of measurement matrices, as well as simulation results of IPA performance, showing the influence of small-size termatiko sets. [ABSTRACT FROM AUTHOR]

In the context of high-dimensional linear regression models, we propose an algorithm of exact support recovery in the setting of noisy compressed sensing where all entries of the design matrix are independent and identically distributed standard Gaussian. This algorithm achieves the same conditions of exact recovery as the exhaustive search (maximal likelihood) decoder, and has an advantage over the latter of being adaptive to all parameters of the problem and computable in polynomial time. The core of our analysis consists in the study of the non-asymptotic minimax Hamming risk of variable selection. This allows us to derive a procedure, which is nearly optimal in a non-asymptotic minimax sense. Then, we develop its adaptive version, and propose a robust variant of the method to handle datasets with outliers and heavy-tailed distributions of observations. The resulting polynomial time procedure is near optimal, adaptive to all parameters of the problem and also robust. [ABSTRACT FROM AUTHOR]

We derive bounds relating Renegar’s condition number to quantities that govern the statistical performance of convex regularization in settings that include the $\ell _{1}$ -analysis setting. Using results from conic integral geometry, we show that the bounds can be made to depend only on a random projection, or restriction, of the analysis operator to a lower dimensional space, and can still be effective if these operators are ill-conditioned. As an application, we get new bounds for the undersampling phase transition of composite convex regularizers. Key tools in the analysis are Slepian’s inequality and the kinematic formula from integral geometry. [ABSTRACT FROM AUTHOR]

In this paper, we study tail inequalities of the largest eigenvalue of a matrix infinitely divisible (i.d.) series, which is a finite sum of fixed matrices weighted by i.d. random variables. We obtain several types of tail inequalities, including Bennett-type and Bernstein-type inequalities. This allows us to further bound the expectation of the spectral norm of a matrix i.d. series. Moreover, by developing a new lower-bound function for $Q(s)=(s+1)\log (s+1)-s$ that appears in the Bennett-type inequality, we derive a tighter tail inequality of the largest eigenvalue of the matrix i.d. series than the Bernstein-type inequality when the matrix dimension is high. The resulting lower-bound function is of independent interest and can improve any Bennett-type concentration inequality that involves the function $Q(s)$. The class of i.d. probability distributions is large and includes Gaussian and Poisson distributions, among many others. Therefore, our results encompass the existing work on matrix Gaussian series as a special case. Lastly, we show that the tail inequalities of a matrix i.d. series have applications in several optimization problems including the chance constrained optimization problem and the quadratic optimization problem with orthogonality constraints. In addition, we also use the resulting tail bounds to show that random matrices constructed from i.d. random variables satisfy the restricted isometry property (RIP) when it acts as a measurement matrix in compressed sensing. [ABSTRACT FROM AUTHOR]

We propose several sampling architectures for the efficient acquisition of an ensemble of correlated signals. We show that without prior knowledge of the correlation structure, each of our architectures (under different sets of assumptions) can acquire the ensemble at a sub-Nyquist rate. Prior to sampling, the analog signals are diversified using simple, implementable components. The diversification is achieved by injecting types of “structured randomness” into the ensemble, the result of which is subsampled. For reconstruction, the ensemble is modeled as a low-rank matrix that we have observed through an (undetermined) set of linear equations. Our main results show that this matrix can be recovered using a convex program when the total number of samples is on the order of the intrinsic degree of freedom of the ensemble — the more heavily correlated the ensemble, the fewer samples are needed. To motivate this study, we discuss how such ensembles arise in the context of array processing. [ABSTRACT FROM AUTHOR]

Noiseless compressed sensing refers to the problem of recovering a (high-dimensional) signal from its under-determined linear measurements. For compressed sensing to be feasible, the signal needs to be structured. While the main focus of the field has been on simple structures such as sparsity, there has been a growing interest in moving beyond sparsity and having a comprehensive compressed sensing framework that covers general structures. Two recent approaches that aim at developing such a framework from different perspectives are i) Quantized maximum a posteriori (Q-MAP), a Bayesian method that assumes full knowledge of the source distribution, and ii) Lagrangian minimum entropy pursuit (L-MEP), a universal recovery method that requires no prior knowledge about the distribution of the source. In this paper, by establishing theoretical connections between L-MEP and Q-MAP, it is shown how the two methods are complementary to each other and lead to a theoretically-founded learning-based recovery method that applies to sources with general structures. Unlike a Bayesian or a universal method, a learning-based method is able to extract the source structure from training data. The effect of error in estimating the source structure on the performance of the learning-based compressed sensing recovery method is characterized. [ABSTRACT FROM AUTHOR]

Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. The main result is the justification of state evolution (SE) equations conjectured by Ma and Ping. This result implies that the EP-based algorithm achieves the Bayes-optimal performance that was originally derived via a non-rigorous tool in statistical physics and proved partially in a recent paper, when the compression rate is larger than a threshold. The proof is based on an extension of a conventional conditioning technique for the standard Gaussian matrix to the case of the Haar matrix. [ABSTRACT FROM AUTHOR]

This work deals with the problem of distributed data acquisition under non-linear communication constraints. More specifically, we consider a model setup where $M$ distributed nodes take individual measurements of an unknown structured source vector $ \boldsymbol {x}_{0}\in \mathbb {R}^{n}$ , communicating their readings simultaneously to a central receiver. Since this procedure involves collisions and is usually imperfect, the receiver measures a superposition of non-linearly distorted signals. In a first step, we will show that an $s$ -sparse vector $ \boldsymbol {x}_{0}$ can be successfully recovered from $ O(s \cdot \log (2n/s)$ of such superimposed measurements, using a traditional Lasso estimator that does not rely on any knowledge about the non-linear corruptions. This direct method however fails to work for several “uncalibrated” system configurations. These blind reconstruction tasks can be easily handled with the $ \ell ^{}$ -Group-Lasso, but coming along with an increased sampling rate of $ O(s\cdot \max \{M, \log (2n/s) \}$ observations — in fact, the purpose of this lifting strategy is to extend a certain class of bilinear inverse problems to non-linear acquisition. Our two algorithmic approaches are a special instance of a more abstract framework which includes sub-Gaussian measurement designs as well as general (convex) structural constraints. These results are of independent interest for various recovery and learning tasks, as they apply to arbitrary non-linear observation models. Finally, to illustrate the practical scope of our theoretical findings, an application to wireless sensor networks is discussed, which actually serves as the prototypical example of our methodology. [ABSTRACT FROM AUTHOR]

This paper treats the recovery of sparse, binary signals through box-constrained basis pursuit using biased measurement matrices. Using a probabilistic model, we provide conditions under which the recovery of both sparse and saturated binary signals is very likely. In fact, we also show that under the same condition, the solution of the boxed-constrained basis pursuit program can be found using boxed-constrained least squares. [ABSTRACT FROM AUTHOR]

We establish the fundamental limits of lossless analog compression by considering the recovery of arbitrary random vectors $ {{ {\mathsf {x}}}} \in {\mathbb R} ^{m}$ from the noiseless linear measurements $ {{ {\mathsf {y}}}} = {{ {A}}} {{ {\mathsf {x}}}} $ with measurement matrix $ {{ {A}}} \in {\mathbb R} ^{n\times m}$. Our theory is inspired by the groundbreaking work of Wu and Verdú (2010) on almost lossless analog compression but applies to the nonasymptotic, i.e., fixed- $m$ case, and considers zero error probability. Specifically, our achievability result states that, for Lebesgue-almost all $ {{ {A}}} $ , the random vector $ {{ {\mathsf {x}}}} $ can be recovered with zero error probability provided that $n>K({{ {\mathsf {x}}}})$ , where $K({{ {\mathsf {x}}}})$ is given by the infimum of the lower modified Minkowski dimension over all support sets $ {\mathcal {U}} $ of $ {{ {\mathsf {x}}}} $ (i.e., sets $ {\mathcal {U}} \subseteq {\mathbb R} ^{m}$ with $ {\mathrm {P}} [ {{ {\mathsf {x}}}} \in {\mathcal {U}} ]=1$). We then particularize this achievability result to the class of $s$ -rectifiable random vectors as introduced in Koliander et al. (2016); these are random vectors of absolutely continuous distribution—with respect to the $s$ -dimensional Hausdorff measure—supported on countable unions of $s$ -dimensional $C^{1}$ -submanifolds of $ {\mathbb R} ^{m}$. Countable unions of $C^{1}$ -submanifolds include essentially all signal models used in the compressed sensing literature such as the standard union of subspaces model underlying much of compressed sensing theory and spectrum-blind sampling, smooth submanifolds, block-sparsity, and low-rank matrices as considered in the matrix completion problem. Specifically, we prove that, for Lebesgue-almost all $ {{ {A}}} $ , $s$ -rectifiable random vectors $ {{ {\mathsf {x}}}} $ can be recovered with zero error probability from $n>s$ linear measurements. This threshold is, however, found not to be tight as exemplified by the construction of an $s$ -rectifiable random vector that can be recovered with zero error probability from $n< s$ linear measurements. Motivated by this observation, we introduce the new class of $s$ -analytic random vectors, which admit a strong converse in the sense of $n\geq s$ being necessary for recovery with probability of error smaller than one. The central conceptual tools in the development of our theory are geometric measure theory and the theory of real analytic functions. [ABSTRACT FROM AUTHOR]

One-bit compressive sensing theory shows that the sparse signals can be almost exactly reconstructed from a small number of one-bit quantized linear measurements. This paper presents the convergence analysis of the binary iterative hard thresholding (BIHT) algorithm which is a state-of-the-art recovery algorithm in one-bit compressive sensing. The basic idea of the convergence analysis is to view BIHT as a kind of projected subgradient method under sparsity constrains. To the best of our knowledge, this is the first convergence analysis of BIHT. We first consider a general convex function subject to sparsity constraints and connect it with the non-convex model in one-bit compressive sensing literatures. A projected subgradient method is proposed to solve the general model and some convergence results are established. A stronger convergence theorem for $\alpha $ –strongly convex functions without assumption on differentiable condition is also established. Furthermore, the corresponding stochastic projected subgradient method is provided with convergence guarantee. In our settings, BIHT is a special case of the projected subgradient method. Therefore, the convergence analysis can be applied to BIHT naturally. Then, we apply the projected subgradient method to some related non-convex optimization models arising in compressive sensing with $\ell _{1}$ -constraint, sparse support vector machines, and rectifier linear units regression. Finally, some numerical examples are presented to show the validity of our convergence analysis. The numerical experiments also show that the proposed projected subgradient method is very simple to implement, robust to sparse noise, and effective for sparse recovery problems. [ABSTRACT FROM AUTHOR]

We study the support recovery problem for compressed sensing, where the goal is to reconstruct the sparsity pattern of a high-dimensional $K$ -sparse signal $\mathrm {x}\in \mathbb {R}^{N}$ , as well as the corresponding sparse coefficients, from low-dimensional linear measurements with and without noise. Our key contribution is a new compressed sensing framework through a new family of carefully designed sparse measurement matrices associated with minimal measurement costs and a low-complexity recovery algorithm. Specifically, the measurement matrix in our framework is designed based on the well-crafted sparsification through capacity-approaching sparse-graph codes, where the sparse coefficients can be recovered efficiently in a few iterations by performing simple error decoding over the observations. We formally connect this general recovery problem with sparse-graph decoding in packet communication systems and analyze our framework in terms of the measurement cost, computational complexity, and recovery performance. Specifically, we show that in the noiseless setting, our framework can recover any arbitrary $K$ -sparse signal in $O(K)$ time using $2K$ measurements asymptotically with a vanishing error probability. In the noisy setting, when the sparse coefficients take values in a finite and quantized alphabet, our framework can achieve the same goal in time $O(K\log (N/K))$ using $O(K\log (N/K))$ measurements obtained from measurement matrix with elements {−1, 0, 1}. When the sparsity $K$ is sub-linear in the signal dimension $K=O(N^\delta)$ for some $0< \delta < 1$ , our results are order-optimal in terms of measurement costs and run-time, both of which are sub-linear in the signal dimension $N$. The sub-linear measurement cost and run-time can also be achieved with continuous-valued sparse coefficients, with a slight increment in the logarithmic factors. More specifically, in the continuous alphabet setting, when $K=O(N^\delta)$ and the magnitudes of all the sparse coefficients are bounded below by a positive constant, our algorithm can recover an arbitrarily large $(1-p)$ -fraction of the support of the sparse signal using $O(K\log (N/K)\log \log (N/K))$ measurements, and $O(K\log ^{1+r}(N/K))$ run-time, where $r$ is an arbitrarily small constant. For each recovered sparse coefficient, we can achieve $O(\epsilon)$ error for an arbitrarily small constant $\epsilon $. In addition, if the magnitudes of all the sparse coefficients are upper bounded by $O(K^{c})$ for some constant $c< 1$ , then we are able to provide a strong $\ell _{1}$ recovery guarantee for the estimated signal $\widehat { \mathrm {x}}$ : $\|\widehat { \mathrm {x}} - \mathrm {x}\|_{1} \le \kappa \| \mathrm {x}\|_{1}$ , where the constant $\kappa $ can be arbitrarily small. This offers the desired scalability of our framework that can potentially enable real-time or near-real-time processing for massive datasets featuring sparsity, which are relevant to a multitude of practical applications. [ABSTRACT FROM AUTHOR]

Evaluating the statistical dimension is a common tool to determine the asymptotic phase transition in compressed sensing problems with Gaussian ensemble. Unfortunately, the exact evaluation of the statistical dimension is very difficult and it has become standard to replace it with an upper-bound. To ensure that this technique is suitable, has introduced an upper-bound on the gap between the statistical dimension and its approximation. In this work, we first show that the error bound in in some low-dimensional models such as total variation and $\ell _{1}$ analysis minimization becomes poorly large. Next, we develop a new error bound which significantly improves the estimation gap compared to. In particular, unlike the bound in that fails in some settings with overcomplete dictionaries, our bound exhibits a decaying behavior in such cases. [ABSTRACT FROM AUTHOR]

This paper revisits a classical scenario in communication theory: a waveform sampled at regular intervals is to be encoded so as to minimize distortion in its reconstruction, despite the noise. This transformation must be online (causal), to enable real-time signaling, and should use no more power than the original signal. The noise model we consider is an atomic norm convex relaxation of the standard (discrete alphabet) Hamming-weight-bounded model, namely adversarial $\ell _{1}$ -bounded. In the block coding (noncausal) setting, such encoding is possible due to the existence of large almost-Euclidean sections in $\ell _{1}$ spaces, a notion first studied in the work of Dvoretzky in 1961. Our main result is that an analogous result is achievable even casually. Equivalently, our work may be seen as a lower triangular version of $\ell _{1}$ Dvoretzky theorems. In terms of communication, the guarantees are expressed in terms of certain time-weighted norms: the time-weighted $\ell _{2}$ norm imposed on the decoder forces increasingly accurate reconstruction of the distant past signal, while the time-weighted $\ell _{1}$ norm on the noise ensures vanishing interference from distant past noise. Encoding is linear (hence easy to implement in analog hardware). Decoding is performed by an LP analogous to those used in compressed sensing. [ABSTRACT FROM AUTHOR]

Sparse superposition codes, or sparse regression codes, constitute a new class of codes, which was first introduced for communication over the additive white Gaussian noise (AWGN) channel. It has been shown that such codes are capacity-achieving over the AWGN channel under optimal maximum-likelihood decoding as well as under various efficient iterative decoding schemes equipped with power allocation or spatially coupled constructions. Here, we generalize the analysis of these codes to a much broader setting that includes all memoryless channels. We show, for a large class of memoryless channels, that spatial coupling allows an efficient decoder, based on the generalized approximate message-passing (GAMP) algorithm, to reach the potential (or Bayes optimal) threshold of the underlying (or uncoupled) code ensemble. Moreover, we argue that spatially coupled sparse superposition codes universally achieve capacity under GAMP decoding by showing, through analytical computations, that the error floor vanishes and the potential threshold tends to capacity, as one of the code parameters goes to infinity. Furthermore, we provide a closed-form formula for the algorithmic threshold of the underlying code ensemble in terms of Fisher information. Relating an algorithmic threshold to a Fisher information has theoretical as well as practical importance. Our proof relies on the state evolution analysis and uses the potential method developed in the theory of low-density parity-check (LDPC) codes and compressed sensing. [ABSTRACT FROM AUTHOR]