2013 ExactSparseRecoverywithL0Projec

• (Li & Zhang, 2013) ⇒ Ping Li, and Cun-Hui Zhang. (2013). “Exact Sparse Recovery with L0 Projections.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487694

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Exact+Sparse+Recovery+with+L0+Projections
• http://dl.acm.org/citation.cfm?id=2487575.2487694&preflayout=flat#citedby

Quotes

Author Keywords

• Compressed sensing; data mining; l0 projections; stable distributions

Abstract

Many applications (e.g., anomaly detection) concern sparse signals. This paper focuses on the problem of recovering a K - sparse signal x ∈ R / 1× N, i.e., K << N and ∑ N / i =1 1{ x _i ≠ 0} = K. In the mainstream framework of compressed sensing (CS), × is recovered from [[M linear measurements y = xS ∈ R / 1× M, where S ∈ R N × M is often a Gaussian (or Gaussian-like) design matrix.

In our proposed method, the design matrix S is generated from an α-stable distribution with α ≈ 0. Our decoding algorithm mainly requires one linear scan of the coordinates, followed by a few iterations on a small number of coordinates which are “undetermined” in the previous iteration. Our practical algorithm consists of two estimators. In the first iteration, the (absolute) minimum estimator is able to filter out a majority of the zero coordinates. The gap estimator, which is applied in each iteration, can accurately recover the magnitudes of the nonzero coordinates. Comparisons with linear programming (LP) and orthogonal matching pursuit (OMP) demonstrate that our algorithm can be significantly faster in decoding speed and more accurate in recovery quality, for the task of exact spare recovery. Our procedure is robust against measurement noise. Even when there are no sufficient measurements, our algorithm can still reliably recover a significant portion of the nonzero coordinates.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 ExactSparseRecoverywithL0Projec	Ping Li Cun-Hui Zhang			Exact Sparse Recovery with L0 Projections				10.1145/2487575.2487694		2013