Sparse approximation

Summary

Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in , signal processing, machine learning, medical imaging, and more. Sparse decomposition Noiseless observations Consider a linear system of equations x = D\alpha, where D is an underdetermined m\times p matrix (m < p) and x \in \mathbb{R}^m,\alpha \in \mathbb{R}^p. The matrix D (typically assumed to be full-rank) is referred to as the dictionary, and x is a signal of interest. The core sparse representation problem is defined as the quest for the sparsest possible representation \alpha satisfying x = D\alpha. Due to the underdetermined nature of D, this linear system admits in general infinitely many possible soluti

Official source

https://en.wikipedia.org/wiki/Sparse_approximation

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (98)

Related publications

Related people (19)

Related people

Related units (6)

Related units

Related concepts (4)

Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solu

Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary D

Sparse dictionary learning (also known as sparse coding or SDL) is a representation learning method which aims at finding a sparse representation of the input data in the form of a linear combination

Related concepts

Related courses (4)

Related courses

Related lectures (9)

Related lectures

Sparse Group Covers and Greedy Tree Approximations

Luca Baldassarre, Volkan Cevher

We consider the problem of finding a K-sparse approximation of a signal, such that the support of the approximation is the union of sets from a given collection, a.k.a. group structure. This problem subsumes the one of finding K-sparse tree approximations. We discuss the tractability of this problem, present a polynomial-time dynamic program for special group structures and propose two novel greedy algorithms with efficient implementations. The first is based on submodular function maximization with knapsack constraints. For the case of tree sparsity, its approximation ratio of 1-1/e is better than current state-of-the-art approximate algorithms. The second algorithm leverages ideas from the greedy algorithm for the Budgeted Maximum Coverage problem and obtains excellent empirical performance, shown by computing the full Pareto frontier of the tree approximations of the wavelet coefficients of an image.

2015

Tractability of interpretability via selection of group-sparse models

Luca Baldassarre, Nirav Bhan, Volkan Cevher

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. A promise of these models is to lead to “interpretable” signals for which we identify its constituent groups, however we show that, in general, claims of correctly identifying the groups with convex relaxations would lead to polynomial time solution algorithms for an NP-hard problem. Instead, leveraging a graph-based understanding of group models, we describe group structures which enable correct model identification in polynomial time via dynamic programming. We also show that group structures that lead to totally unimodular constraints have tractable relaxations. Finally, we highlight the non-convexity of the Pareto frontier of group-sparse approximations and what it means for tractability.

2013

A Game Theoretic Approach to Expander-based Compressive Sensing

Volkan Cevher, Sina Jafarpour

We consider the following expander-based compressive sensing (e-CS) problem: Given Φ ∈ ℝM×N (M

IEEE2011