TY - GEN
T1 - Compressive sensing meets game theory
AU - Jafarpour, Sina
AU - Schapire, Robert E.
AU - Cevher, Volkan
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - We introduce the Multiplicative Update Selector and Estimator (MUSE) algorithm for sparse approximation in under-determined linear regression problems. Given f = Φα* + μ, the MUSE provably and efficiently finds a k-sparse vector α such that ∥Φα - f∥∞ ≤ ∥μ∥∞ + O (1/√k), for any k-sparse vector α*, any measurement matrix Φ, and any noise vector μ. We cast the sparse approximation problem as a zero-sum game over a properly chosen new space; this reformulation provides salient computational advantages in recovery. When the measurement matrix Φ provides stable embedding to sparse vectors (the so-called restricted isometry property in compressive sensing), the MUSE also features guarantees on ∥α* - α∥2. Simulation results demonstrate the scalability and performance of the MUSE in solving sparse approximation problems based on the Dantzig Selector.
AB - We introduce the Multiplicative Update Selector and Estimator (MUSE) algorithm for sparse approximation in under-determined linear regression problems. Given f = Φα* + μ, the MUSE provably and efficiently finds a k-sparse vector α such that ∥Φα - f∥∞ ≤ ∥μ∥∞ + O (1/√k), for any k-sparse vector α*, any measurement matrix Φ, and any noise vector μ. We cast the sparse approximation problem as a zero-sum game over a properly chosen new space; this reformulation provides salient computational advantages in recovery. When the measurement matrix Φ provides stable embedding to sparse vectors (the so-called restricted isometry property in compressive sensing), the MUSE also features guarantees on ∥α* - α∥2. Simulation results demonstrate the scalability and performance of the MUSE in solving sparse approximation problems based on the Dantzig Selector.
KW - Compressed Sensing
KW - Dantzig Selector
KW - Game Theory
KW - Multiplicative Weights Algorithm
UR - http://www.scopus.com/inward/record.url?scp=80051636362&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051636362&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2011.5947144
DO - 10.1109/ICASSP.2011.5947144
M3 - Conference contribution
AN - SCOPUS:80051636362
SN - 9781457705397
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 3660
EP - 3663
BT - 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings
T2 - 36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011
Y2 - 22 May 2011 through 27 May 2011
ER -