A typical reconstruction limit of compressed sensing based on Lp-norm minimization

Abstract

We consider the problem of reconstructing an $N$-dimensional continuous vector $\bx$ from $P$ constraints which are generated by its linear transformation under the assumption that the number of non-zero elements of $\bx$ is typically limited to $\rho N$ ($0\le \rho \le 1$). Problems of this type can be solved by minimizing a cost function with respect to the $L_p$-norm $||\bx||_p=\lim_{ε\to +0}\sum_{i=1}^N |x_i|^{p+ε}$, subject to the constraints under an appropriate condition. For several $p$, we assess a typical case limit ${\alpha }_c(\rho )$, which represents a critical relation between $\alpha =P/N$ and $\rho$ for successfully reconstructing the original vector by minimization for typical situations in the limit $N,P\to \infty$ with keeping $\alpha$ finite, utilizing the replica method. For $p=1$, ${\alpha }_c(\rho )$ is considerably smaller than its worst case counterpart, which has been rigorously derived by existing literature of information theory.

12 pages, 2 figures

References in corpus (1)

• Analysis of CDMA systems that are characterized by eigenvalue spectrum

Cited by in corpus (59)

• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Statistical physics of inference: Thresholds and algorithms
• Universality in polytope phase transitions and message passing algorithms
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Statistical physics-based reconstruction in compressed sensing
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Generalisation error in learning with random features and the hidden manifold model
• Statistical mechanics of complex neural systems and high dimensional data
• The Mutual Information in Random Linear Estimation
• Cross validation in LASSO and its acceleration
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Networking - A Statistical Physics Perspective
• Sparse Modeling in Quantum Many-Body Problems
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Generalized Turbo Signal Recovery for Nonlinear Measurements and Orthogonal Sensing Matrices
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)
• Statistical Mechanics of Dictionary Learning
• Bayesian signal reconstruction for 1-bit compressed sensing
• Teacher-student learning for a binary perceptron with quantum fluctuations
• Optimal incorporation of sparsity information by weighted ${\ell }_1$ optimization
• Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
• Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
• A statistical mechanics approach to de-biasing and uncertainty estimation in LASSO for random measurements
• Statistical mechanics of low-rank tensor decomposition
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• RSB Decoupling Property of MAP Estimators
• Compressed sensing reconstruction using Expectation Propagation
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Effective implementation of $l_0$-Regularised Compressed Sensing with Chaotic-Amplitude-Controlled Coherent Ising Machines
• Online compressed sensing
• Asymptotic Performance Analysis of a K-Hop Amplify-and-Forward Relay MIMO Channel
• Typical $l_1$-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
• Statistical mechanics approach to 1-bit compressed sensing
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Blind Sensor Calibration using Approximate Message Passing
• Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing
• Active pooling design in group testing based on Bayesian posterior prediction
• Sparse approximation problem: how rapid simulated annealing succeeds and fails
• Sparse Hopfield network reconstruction with ${\ell }_1$ regularization
• Evaluation of Generalized Degrees of Freedom for Sparse Estimation by Replica Method
• Phase transition in compressed sensing with horseshoe prior
• ${\ell }_1$-penalized Multinomial Regression: Estimation, inference, and prediction, with an application to risk factor identification for different dementia subtypes
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Critical Behavior and Universality Classes for an Algorithmic Phase Transition in Sparse Reconstruction
• Phase transition in binary compressed sensing based on $L_1$-norm minimization
• Dynamic crossover in the persistence probability of manifolds at criticality
• Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search
• Analysis of Sparse Representations Using Bi-Orthogonal Dictionaries
• Replica Analysis for Ensemble Techniques in Variable Selection
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• Stability of the replica symmetric solution in diluted perceptron learning
• Statistical mechanics analysis of thresholding 1-bit compressed sensing
• Expectation propagation on the diluted Bayesian classifier
• Typical reconstruction limit and phase transition of maximum entropy method
• Effect of global shrinkage parameter of horseshoe prior in compressed sensing
• A study of the universal threshold in the L1 recovery by statistical mechanics