Phase transition in binary compressed sensing based on -norm minimization
arXiv:2405.16824 · doi:10.7566/JPSJ.93.084003
Abstract
Compressed sensing is a signal processing scheme that reconstructs high-dimensional sparse signals from a limited number of observations. In recent years, various problems involving signals with a finite number of discrete values have been attracting attention in the field of compressed sensing. In particular, binary compressed sensing, which restricts signal elements to binary values , is the most fundamental and straightforward analysis subject in such problem settings. We evaluate the typical performance of noiseless binary compressed sensing based on -norm minimization using the replica method, a statistical mechanical approach. We analyze a general setting where the elements of the observation matrix follow a Gaussian distribution, including a non-zero mean. We demonstrate that the biased observation matrix indicates more reconstruction success conditions in binary compressed sensing. Our results are consistent with the outcomes of several prior studies.
14 pages, 2 Figures
References in corpus (22)
- Nearly unbiased variable selection under minimax concave penalty
- Message Passing Algorithms for Compressed Sensing
- Boolean Compressed Sensing and Noisy Group Testing
- Statistical physics-based reconstruction in compressed sensing
- Compressing Green's function using intermediate representation between imaginary-time and real-frequency domains
- Energy landscape analysis of neuroimaging data
- A typical reconstruction limit of compressed sensing based on Lp-norm minimization
- Sparse modeling approach to analytical continuation of imaginary-time quantum Monte Carlo data
- On Convergence of Approximate Message Passing
- Sparse Modeling in Quantum Many-Body Problems
- Overcomplete compact representation of two-particle Green's functions
- SpM: Sparse modeling tool for analytic continuation of imaginary-time Green's function
- Detection of cheating by decimation algorithm
- Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
- Recovery of binary sparse signals from compressed linear measurements via polynomial optimization
- Quantum Annealing Based Binary Compressive Sensing with Matrix Uncertainty
- Quantitative Group Testing and the rank of random matrices
- L_1-regularized Boltzmann machine learning using majorizer minimization
- Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
- Spatio-temporal reconstruction of substance dynamics using compressed sensing in multi-spectral magnetic resonance spectroscopic imaging
- Phase transition in compressed sensing with horseshoe prior
- Sparse Signal Reconstruction with QUBO Formulation in l0-regularized Linear Regression