Expander \ell₀-Decoding

DOI10.1016/J.ACHA.2017.03.001arXiv1508.01256MaRDI QIDQ6264259FDOQ6264259

Authors: Rodrigo Mendoza-Smith, Jared Tanner

Publication date: 5 August 2015

Abstract: We introduce two new algorithms, Serial-

e l l_{0}

and Parallel-

e l l_{0}

for solving a large underdetermined linear system of equations

y = A x i n m a t h b b R^{m}

when it is known that

x i n m a t h b b R^{n}

has at most

k < 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). Serial-

e l l_{0}

and Parallel-

e l l_{0}

iteratively minimise

| y - A h a t x |_{0}

by successfully combining two desirable features of previous CCS algorithms: the information-preserving strategy of ER, and the parallel updating mechanism of SMP. We are able to link these elements and guarantee convergence in

m a t h c a l O (d n l o g k)

operations by assuming that the signal is dissociated, meaning that all of the

2^{k}

subset sums of the support of

x

are pairwise different. However, we observe empirically that the signal need not be exactly dissociated in practice. Moreover, we observe Serial-

e l l_{0}

and Parallel-

e l l_{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 particular, they are able to reliably solve for a

k

-sparse vector

x i n m a t h b b R^{n}

from

m

expander measurements with

n / m = 1 0^{3}

and

k / m

up to four times greater than what is achievable by

e l l_{1}

-regularization from dense Gaussian measurements. Additionally, Serial-

e l l_{0}

and Parallel-

e l l_{0}

are observed to be able to solve large problems sizes in substantially less time than other algorithms for compressed sensing. In particular, Parallel-

e l l_{0}

is structured to take advantage of massively parallel architectures.

Mathematics Subject Classification ID

Numerical analysis (65-XX) Information and communication theory, circuits (94-XX)

This page was built for publication: Expander $\ell_0$-Decoding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6264259)