NDLI: Beyond sparsity: Recovering structured representations by ${\ell}^1$ minimization and greedy algorithms

Content Provider	Springer Nature Link
Author	Gribonval, Rémi Nielsen, Morten
Copyright Year	2006
Abstract	Finding a sparse approximation of a signal from an arbitrary dictionary is a very useful tool to solve many problems in signal processing. Several algorithms, such as Basis Pursuit (BP) and Matching Pursuits (MP, also known as greedy algorithms), have been introduced to compute sparse approximations of signals, but such algorithms a priori only provide sub-optimal solutions. In general, it is difficult to estimate how close a computed solution is from the optimal one. In a series of recent results, several authors have shown that both BP and MP can successfully recover a sparse representation of a signal provided that it is sparse enough, that is to say if its support (which indicates where are located the nonzero coefficients) is of sufficiently small size. In this paper we define identifiable structures that support signals that can be recovered exactly by ${\ell}^1$ minimization (Basis Pursuit) and greedy algorithms. In other words, if the support of a representation belongs to an identifiable structure, then the representation will be recovered by BP and MP. In addition, we obtain that if the output of an arbitrary decomposition algorithm is supported on an identifiable structure, then one can be sure that the representation is optimal within the class of signals supported by the structure. As an application of the theoretical results, we give a detailed study of a family of multichannel dictionaries with a special structure (corresponding to the representation problem $X = {{A}}S\mathbf{\Phi-7\Phi}^T$ ) often used in, e.g., under-determined source sepa-ration problems or in multichannel signal processing. An identifiable structure for such dictionaries is defined using a generalization of Tropp’s Babel function which combines the coherence of the mixing matrix ${{A}}$ with that of the time-domain dictionary ${\mathbf{\Phi-7\Phi}}$ , and we obtain explicit structure conditions which ensure that both $\ell^1$ minimization and a multi-channel variant of Matching Pursuit can recover structured multichannel representations. The multichannel Matching Pursuit algorithm is described in detail and we conclude with a discussion of some implications of our results in terms of blind source separation based on sparse decompositions.
Ending Page	41
Page Count	19
Starting Page	23
File Format	PDF
ISSN	10197168
e-ISSN	15729044
Journal	Advances in Computational Mathematics
Issue Number	1
Volume Number	28
Language	English
Publisher	Springer US
Publisher Date	2006-11-25
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation by other special function classes multichannel representations sparse component analysis Numeric Computing linear programming Theory of Computation Mathematics $\ell^1$ -minimization basis pursuit algorithm Algebra Calculus of Variations and Optimal Control; Optimization sparse approximations greedy algorithm
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computational Mathematics

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

Beyond coherence : recovering structured time-frequency representations

Beyond coherence : recovering structured time-frequency representations

Beyond sparsity : recovering structured representations by $\\ell^1$-minimization and greedy algorithms.

Further Results on Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise

An Improved Smoothed $ell^0$ Approximation Algorithm for Sparse Representation

Greedy approximation with regard to non-greedy bases

Outlier-Robust Greedy Pursuit Algorithms in $ell _{p}$ -Space for Sparse Approximation

Adaptive Sparsity Matching Pursuit Algorithm for Sparse Reconstruction

Simultaneous approximation by greedy algorithms

Beyond sparsity: Recovering structured representations by ${\ell}^1$ minimization and greedy algorithms

Similar Documents

Beyond coherence : recovering structured time-frequency representations

Beyond coherence : recovering structured time-frequency representations

Beyond sparsity : recovering structured representations by $\\ell^1$-minimization and greedy algorithms.

Further Results on Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise

An Improved Smoothed $ell^0$ Approximation Algorithm for Sparse Representation

Greedy approximation with regard to non-greedy bases

Outlier-Robust Greedy Pursuit Algorithms in $ell _{p}$ -Space for Sparse Approximation

Adaptive Sparsity Matching Pursuit Algorithm for Sparse Reconstruction

Simultaneous approximation by greedy algorithms

Beyond sparsity: Recovering structured representations by ${\ell}^1$ minimization and greedy algorithms