Abstract
We explore the application of a homotopy continuation-based method for sparse signal representation in overcomplete dictionaries. Our problem setup is based on the basis pursuit framework, which involves a convex optimization problem consisting of terms enforcing data fidelity and sparsity, balanced by a regularization parameter. Choosing a good regularization parameter in this framework is a challenging task. We describe a homotopy continuation-based algorithm to find and trace efficiently all solutions of basis pursuit as a function of the regularization parameter. In addition to providing an attractive alternative to existing optimization methods for solving the basis pursuit problem, this algorithm can also be used to provide an automatic choice for the regularization parameter, based on prior information about the desired number of non-zero components in the sparse representation. Our numerical examples demonstrate the effectiveness of this algorithm in accurately and efficiently generating entire solution paths for basis pursuit, as well as producing reasonable regularization parameter choices. Furthermore, exploring the resulting solution paths in various operating conditions reveals insights about the nature of basis pursuit solutions.
Keywords
Basis pursuitRegularization (linguistics)HomotopySparse approximationContinuationMathematical optimizationBasis functionRepresentation (politics)Computer scienceAlgorithmOptimization problemMathematicsBasis (linear algebra)Matching pursuitArtificial intelligenceCompressed sensing
Affiliated Institutions
Related Publications
Greed is Good: Algorithmic Results for Sparse Approximation
This article presents new results on using a greedy algorithm, orthogonal matching pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries. It provi...
Image decomposition via the combination of sparse representations and a variational approach
The separation of image content into semantic parts plays a vital role in applications such as compression, enhancement, restoration, and more. In recent years, several pioneeri...
$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
In recent years there has been a growing interest in the study of sparse representation of signals. Using an overcomplete dictionary that contains prototype signal-atoms, signal...
An Equivalence Between Sparse Approximation and Support Vector Machines
This article shows a relationship between two different approximation techniques: the support vector machines (SVM), proposed by V. Vapnik (1995) and a sparse approximation sche...
Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems
Many problems in signal processing and statistical inference involve finding sparse solutions to under-determined, or ill-conditioned, linear systems of equations. A standard ap...
Publication Info
- Year
- 2006
- Type
- article
- Volume
- 5
- Pages
- 733-736
- Citations
- 271
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
271
OpenAlex
Cite This
Dmitry Malioutov,
Müjdat Çetin,
Alan S. Willsky
(2006).
Homotopy continuation for sparse signal representation.
, 5
, 733-736.
https://doi.org/10.1109/icassp.2005.1416408
Identifiers
- DOI
- 10.1109/icassp.2005.1416408