Expander ℓ0-decoding

Author: 

Mendoza-Smith, R
Tanner, J

Publication Date: 

9 March 2017

Journal: 

Applied and Computational Harmonic Analysis

Last Updated: 

2020-01-21T22:50:58.31+00:00

Issue: 

3

Volume: 

45

DOI: 

10.1016/j.acha.2017.03.001

page: 

642-667

abstract: 

<p>We introduce two new algorithms, Serial-ℓ0 and Parallel-ℓ0 for solving a large underdetermined linear system of equations y = Ax ∈ ℝm when it is known that x ∈ ℝn has at most k &lt; m nonzero entries and that A is the adjacency matrix of an unbalanced left d-regular expander graph. The matrices in this class are sparse and allow a highly efficient implementation. A number of algorithms have been designed to work exclusively under this setting, composing the branch of combinatorial compressed-sensing (CCS).</p> <br/> <p>Serial-ℓ0 and Parallel-ℓ0 iteratively minimise ||y - Ax^||0 by successfully combining two desirable features of previous CCS algorithms: the coordinate selection strategy of ER for updating x^, and the parallel updating mechanism of SMP. We are able to link these elements and guarantee convergence in O(dn log k) operations by introducing a randomized scaling of columns in A, with scaling chosen independent of the measured vector. We also empirically observe that the recovery properties of Serial-ℓ0 and Parallel-ℓ0 degrade gracefully as the signal is allowed to have its non-zero values chosen adversarially.</p> <br/> <p>Moreover, we observe Serial-ℓ0 and Parallel-ℓ0 to be able to solve large scale problems with a larger fraction of nonzeros than other algorithms when the number of measurements is substantially less than the signal length; in particu- lar, they are able to reliably solve for a k-sparse vector x ∈ ℝn from m expander measurements with n=m = 10^3 and k/m up to four times greater than what is achievable by ℓ1-regularization from dense Gaussian measurements. Additionally, due to their low computational complexity, Serial-ℓ0 and Parallel-ℓ0 are observed to be able to solve large problems sizes in substantially less time than other algorithms for compressed sensing. In particular, Parallel-ℓ0 is structured to take advantage of massively parallel architectures.</p>

Symplectic id: 

685459

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article