NDLI: On the Stable Recovery of the Sparsest Overcomplete Representations in Presence of Noise

Content Provider	IEEE Xplore Digital Library
Author	Babaie-Zadeh, M. Jutten, C.
Copyright Year	1991
Abstract	Let x be a signal to be sparsely decomposed over a redundant dictionary A, i.e., a sparse coefficient vector s has to be found such that x = As. It is known that this problem is inherently unstable against noise, and to overcome this instability, Donoho, Elad and Temlyakov ["Stable recovery of sparse overcomplete representations in the presence of noise," IEEE Trans. Inf. Theory, vol. 52, no. 1, pp. 6-18, Jan. 2006] have proposed to use an "approximate" decomposition, that is, a decomposition satisfying ∥x - As∥₂ ≤ δ rather than satisfying the exact equality x = As. Then, they have shown that if there is a decomposition with ∥s∥₀ <;; (1 + M^-1)/2, where M denotes the coherence of the dictionary, this decomposition would be stable against noise. On the other hand, it is known that a sparse decomposition with ∥s∥₀ <;; (1/2)spark(A) is unique. In other words, although a decomposition with ∥s∥₀ <;; (1/2)spark(A) is unique, its stability against noise has been proved only for highly more restrictive decompositions satisfying ∥s∥₀ <;; (1 + M^-1)/2, because usually (1 + M^-1)/2 ≪ (1/2)spark(A). This limitation maybe had not been very important before, because ∥s∥₀ <;; (1 + M^-1)/2 is also the bound which guaranties that the sparse decomposition can be found via minimizing the l¹ norm, a classic approach for sparse decomposition. However, with the availability of new algorithms for sparse decomposition, namely SL0 and robust-SLO, it would be important to know whether or not unique sparse decompositions with (1 + M^-1)/2 ≤ ∥s∥₀ <;; (1/2)spark(A) are stable. In this correspondence, we show that such decompositions are indeed stable. In other words, we extend the stability bound from ∥s∥₀ <;; (1 + M^-1)/2 to the whole uniqueness range ∥s∥0 <;; (1/2)spark(A). In summary, we show that all unique sparse decompositions are stably recoverable. Moreover, we see that sparser decompositions are "more stable".
Sponsorship	IEEE Signal Processing Society
Starting Page	5396
Ending Page	5400
Page Count	5
File Size	179284
File Format	PDF
ISSN	1053587X
Volume Number	58
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-10-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	Dictionaries Stability Permission Collaborative work International collaboration Compressed sensing Matrix decomposition Linear systems Senior members Signal processing algorithms sparse signal decomposition overcomplete dictionaries sparse component analysis (SCA) sparse recovery
Content Type	Text
Resource Type	Article
Subject	Signal Processing Electrical and Electronic Engineering

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

Sparse Decomposition over non-full-rank dictionaries

Corrections to “On the Stable Recovery of the Sparsest Overcomplete Representations in Presence of Noise” [Oct 10 5396-5400]

A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $ell ^{0}$ Norm

Stable recovery of sparse overcomplete representations in the presence of noise

Robust-SL0 for stable sparse representation in noisy settings

Bayesian Pursuit algorithm for sparse representation

Stable recovery of sparse overcomplete representations in the presence of noise (2006)

Thresholded $smoothed-ℓ^{0}(SL0)$ dictionary learning for sparse representations

Sparse Decomposition Over Non-Full-Rank Dictionaries

On the Stable Recovery of the Sparsest Overcomplete Representations in Presence of Noise

Similar Documents

Sparse Decomposition over non-full-rank dictionaries

Corrections to “On the Stable Recovery of the Sparsest Overcomplete Representations in Presence of Noise” [Oct 10 5396-5400]

A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $ell ^{0}$ Norm

Stable recovery of sparse overcomplete representations in the presence of noise

Robust-SL0 for stable sparse representation in noisy settings

Bayesian Pursuit algorithm for sparse representation

Stable recovery of sparse overcomplete representations in the presence of noise (2006)

Thresholded $smoothed-ℓ^{0}(SL0)$ dictionary learning for sparse representations

Sparse Decomposition Over Non-Full-Rank Dictionaries

On the Stable Recovery of the Sparsest Overcomplete Representations in Presence of Noise