Name
Abstract | ||
|---|---|---|
We present the first deterministic measurement matrix construction with an order-optimal number of rows for sparse signal reconstruction. This improves the measurements required in prior constructions and addresses a known open problem in the theory of sparse signal recovery. Our construction uses adjacency matrices of bipartite graphs that have large girth. The main result is that girth (the length of the shortest cycle in the graph) can be used as a certificate that a measurement matrix can recover almost all sparse signals. Specifically, our matrices guarantee recovery “for-each” sparse signal under basis pursuit. Our techniques are coding theoretic and rely on a recent connection of compressed sensing to LP relaxations for channel decoding. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ICASSP.2013.6638795 | Acoustics, Speech and Signal Processing |
Keywords | Field | DocType |
channel coding,compressed sensing,graph theory,matrix algebra,signal reconstruction,LP relaxations,adjacency matrices,bipartite graphs,channel decoding,deterministic measurement matrix construction,optimal deterministic compressed sensing matrices,order-optimal number,sparse signal reconstruction,sparse signal recovery | Adjacency matrix,Graph theory,Mathematical optimization,Computer science,Matrix (mathematics),Sparse approximation,Basis pursuit,Restricted isometry property,Sparse matrix,Compressed sensing | Conference |
ISSN | Citations | PageRank |
1520-6149 | 10 | 0.54 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arash Saber Tehrani | 1 | 99 | 6.41 |
| Alexandros G. Dimakis | 2 | 3575 | 206.71 |
| Giuseppe Caire | 3 | 9797 | 807.61 |