Does ℓ_p-minimization outperform ℓ₁-minimization?

2015/01/15 by Le Zheng, Zheng, Le, Arian Maleki +6 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1501.03704

openalex publication_date 2015/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In many application areas we are faced with the following question: Can we recover a sparse vector x_o ∈ ℝ^N from its undersampled set of noisy observations y ∈ ℝⁿ, y=A x_o+w. The last decade has witnessed a surge of algorithms and theoretical results addressing this question. One of the most popular algorithms is the ℓ_p-regularized least squares (LPLS) given by the following formulation: x(γ,p )∈ argmin_x (1)/(2)‖y - Ax‖₂²+γ‖x‖_p^p, where p ∈ [0,1]. Despite the non-convexity of these problems for p<1, they are still appealing because of the following folklores in compressed sensing: (i) x(γ,p ) is closer to x_o than x(γ,1). (ii) If we employ iterative methods that aim to converge to a local minima of LPLS, then under good initialization these algorithms converge to a solution that is closer to x_o than x(γ,1). In spite of the existence of plenty of empirical results that support these folklore theorems, the theoretical progress to establish them has been very limited. This paper aims to study the above folklore theorems and establish their scope of validity. Starting with approximate message passing algorithm as a heuristic method for solving LPLS, we study the impact of initialization on the performance of AMP. Then, we employ the replica analysis to show the connection between the solution of AMP and x(γ, p) in the asymptotic settings. This enables us to compare the accuracy of x(γ,p) for p ∈ [0,1]. In particular, we will characterize the phase transition and noise sensitivity of LPLS for every 0≤ p≤ 1 accurately. Our results in the noiseless setting confirm that LPLS exhibits the same phase transition for every 0≤ p <1 and this phase transition is much higher than that of LASSO.

Citations

• Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
• Stein COnsistent Risk Estimator (SCORE) for hard thresholding
• Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0<q⩽1
• Estimation of the Mean of a Multivariate Normal Distribution

Cited by

• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques

Related

• Low noise sensitivity analysis of Lq-minimization in oversampled systems
• Compressed Sensing over ℓ_p-balls: Minimax Mean Square Error
• Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
• Stable Recovery of Sparse Signals via l_p-Minimization
• Stable reconstructions for the analysis formulation of ℓ^p-minimization using redundant systems