Özet

Given a redundant dictionary Φ, represented by an M×N matrix (Φ∈RM×N) and a target signal y∈RM, the sparse approximation problem asks to find an approximate representation of y using a linear combination of at most k atoms. This note presents a hardness result for sparse approximation problem under a measure of quality, which is essentially the squared multiple correlation in statistical analysis. We show that unless P=NP, all polynomial time algorithms which provide a k-sparse vector x should satisfy where x⁎ is the optimal k-sparse solution and Φx denotes the column sub-matrix of Φ which consists of the column vectors with indices of non-zero elements in x. We relate this result to the recent algorithmic results of Das and Kempe (2008, 2011) [1,2] and conclude that Forward Regression and Orthogonal Matching Pursuit are almost the best one can hope for solving the sparse approximation problem …

Anahtar Kelimeler

Approximation algorithms | Complexity | Computational complexity | Inapproximability | Sparse approximation | Subset selection

Science Direct

Atıf Sayıları
Web of Science	3
Scopus	4
Google Scholar	7

A note on the hardness of sparse approximation

Paylaş