Further Results on Performance Analysis for Compressive Sensing Using Expander Graphs

Weiyu Xu; Babak Hassibi

doi:10.1109/ACSSC.2007.4487288

Back

Conference proceeding

Further Results on Performance Analysis for Compressive Sensing Using Expander Graphs

Weiyu Xu and Babak Hassibi

2007 Conference Record of the Forty-First Asilomar Conference on Signals, Systems and Computers, pp.621-625

11/2007

DOI: 10.1109/ACSSC.2007.4487288

View Online

Abstract

Compressive sensing is an emerging technology which can recover a sparse signal vector of dimension n via a much smaller number of measurements than n. In this paper, we will give further results on the performance bounds of compressive sensing. We consider the newly proposed expander graph based compressive sensing schemes and show that, similar to the l 1 minimization case, we can exactly recover any k-sparse signal using only O(k log(n)) measurements, where k is the number of nonzero elements. The number of computational iterations is of order O(k log(n)), while each iteration involves very simple computational steps.

Mathematics

Signal Processing

Current measurement

Graph theory

Noise robustness

Performance analysis

Signal sampling

Sparse matrices

Time measurement

Upper bound

Details

Title: Subtitle: Further Results on Performance Analysis for Compressive Sensing Using Expander Graphs
Creators: Weiyu Xu - California Institute of Technology
Babak Hassibi - California Institute of Technology
Resource Type: Conference proceeding
Publication Details: 2007 Conference Record of the Forty-First Asilomar Conference on Signals, Systems and Computers, pp.621-625
DOI: 10.1109/ACSSC.2007.4487288
ISSN: 1058-6393
eISSN: 2576-2303
Publisher: IEEE
Language: English
Date published: 11/2007
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984197545702771

Metrics

7 Record Views