NDLI: On the Performance of Sparse Recovery Via <formula formulatype=inline><tex Notation=TeX>$ell_p$</tex></formula>-Minimization <formula formulatype=inline><tex Notation=TeX>$(0 leq p leq 1)$</tex></formula>

Content Provider	IEEE Xplore Digital Library
Author	Meng Wang Weiyu Xu Ao Tang
Copyright Year	1963
Abstract	It is known that a high-dimensional sparse vector x* in TV can be recovered from low-dimensional measurements y = Ax* where A^m×n(m <; n) is the measurement matrix. In this paper, with A being a random Gaussian matrix, we investigate the recovering ability of ℓ_p-minimization (0 ≤ p ≤ 1) as p varies, where ℓ_p-minimization returns a vector with the least ℓ_p quasi norm among all the vectors x satisfying Ax = y. Besides analyzing the performance of strong recovery where ℓ_p-minimization is re quired to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of "weak" recovery of ℓ_p -minimization (0 ≤ p <; 1) where the aim is to recover all the sparse vectors on one support with a fixed sign pattern. When α(:= ^m/_n) → 1, we provide sharp thresholds of the sparsity ratio (i.e., percentage of nonzero entries of a vector) that differentiates the success and failure via ℓ_p -minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0, 1), while the threshold is 1 for ℓ₁-minimization. We also explicitly demonstrate that ℓ_p-minimization (p <; 1) can re turn a denser solution than ℓ_p-minimization. For any a G (0.1), we provide bounds of the sparsity ratio for strong recovery and weak recovery, respectively, below which ℓ_p-minimization succeeds. Our bound of strong recovery improves on the existing bounds when a is large. In particular, regarding the recovery threshold, this paper argues that ℓ_p-minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and ℓ_p -minimization can outperform ℓ_p-minimization for weak recovery. These are in contrast to traditional wisdom that ℓ_p-minimization, though computationally more expensive, always has better sparse recovery ability than ℓ₀ -minimization since it is closer to ℓ₁-minimization. Finally, we provide an intuitive explanation to our findings. Numerical examples are also used to un ambiguously confirm and illustrate the theoretical predictions.
Sponsorship	IEEE Information Theory Society
Starting Page	7255
Ending Page	7278
Page Count	24
File Size	1228159
File Format	PDF
ISSN	00189448
Volume Number	57
Issue Number	11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-11-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Minimization Null space Support vector machines Sparse matrices Compressed sensing sparse recovery $\ell_p$ -minimization phase transition recovery threshold
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Precise Stability Phase Transitions for $ell_1$ Minimization: A Unified Geometric Framework

Compressed Sensing Matrices From Fourier Matrices

Sparse Recovery From Combined Fusion Frame Measurements

Weighted one-norm minimization with inaccurate support estimates: Sharp analysis via the null-space property

On the performance of sparse recovery via `p-minimization (0 p 1).

Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

Robustness of Sparse Recovery via $F$ -Minimization: A Topological Viewpoint

Sparse signal recovery with additional ℓ2 null space constraint

Exact Recoverability From Dense Corrupted Observations via $ell _{1}$-Minimization

On the Performance of Sparse Recovery Via $ell_p$-Minimization $(0 leq p leq 1)$

Similar Documents

Precise Stability Phase Transitions for $ell_1$ Minimization: A Unified Geometric Framework

Compressed Sensing Matrices From Fourier Matrices

Sparse Recovery From Combined Fusion Frame Measurements

Weighted one-norm minimization with inaccurate support estimates: Sharp analysis via the null-space property

On the performance of sparse recovery via `p-minimization (0 p 1).

Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

Robustness of Sparse Recovery via $F$ -Minimization: A Topological Viewpoint

Sparse signal recovery with additional ℓ2 null space constraint

Exact Recoverability From Dense Corrupted Observations via $ell _{1}$-Minimization

On the Performance of Sparse Recovery Via $ell_p$-Minimization $(0 leq p leq 1)$