CaltechAUTHORS
  A Caltech Library Service

Recovering Jointly Sparse Signals via Joint Basis Pursuit

Oymak, Samet and Hassibi, Babak (2012) Recovering Jointly Sparse Signals via Joint Basis Pursuit. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20150126-075526346

[img] PDF - Submitted Version
See Usage Policy.

154Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150126-075526346

Abstract

This work considers recovery of signals that are sparse over two bases. For instance, a signal might be sparse in both time and frequency, or a matrix can be low rank and sparse simultaneously. To facilitate recovery, we consider minimizing the sum of the ℓ_1-norms that correspond to each basis, which is a tractable convex approach. We find novel optimality conditions which indicates a gain over traditional approaches where ℓ_1 minimization is done over only one basis. Next, we analyze these optimality conditions for the particular case of time-frequency bases. Denoting sparsity in the first and second bases by k_1,k_2 respectively, we show that, for a general class of signals, using this approach, one requires as small as O(max{k_1,k_2} log log n) measurements for successful recovery hence overcoming the classical requirement of Θ(min{k_1,k_2} log (n/(min{k_1,k_2})) for ℓ _1 minimization when k_1 ≈ k_2. Extensive simulations show that, our analysis is approximately tight.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1202.3531arXivDiscussion Paper
Additional Information:This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CCF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking.
Funders:
Funding AgencyGrant Number
NSFCCF-0729203
NSFCNS-0932428
NSFCCF-1018927
Office of Naval Research (ONR)N00014-08-1-0747
Caltech’s Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:basis pursuit, compressed sensing, phase re- trieval, duality, convex optimization
Record Number:CaltechAUTHORS:20150126-075526346
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150126-075526346
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54054
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:26 Jan 2015 18:55
Last Modified:26 Jan 2015 18:55

Repository Staff Only: item control page