Expander ℓ<inf>0</inf>-decoding

© 2017 We introduce two new algorithms, Serial-ℓ0and Parallel-ℓ0for solving a large underdetermined linear system of equations y=Ax∈Rmwhen it is known that x∈Rnhas 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-ℓ0and Parallel-ℓ0iteratively minimise ‖y−Axˆ‖0by successfully combining two desirable features of previous CCS algorithms: the coordinate selection strategy of ER [1] for updating xˆ and the parallel updating mechanism of SMP [2]. We are able to link these elements and guarantee convergence in O(dnlog⁡k) operations by introducing a randomised scaling of columns in A, with scaling chosen independent of the measured vector. We also empirically observe that the recovery properties of Serial-ℓ0and Parallel-ℓ0degrade gracefully as the signal is allowed to have its non-zero values chosen adversarially. Moreover, we observe Serial-ℓ0and Parallel-ℓ0to 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∈Rnfrom m expander measurements with n/m=103and k/m up to four times greater than what is achievable by ℓ1-regularisation from dense Gaussian measurements. Additionally, due to their low computational complexity, Serial-ℓ0and Parallel-ℓ0are observed to be able to solve large problems sizes in substantially less time than other algorithms for compressed sensing. In particular, Parallel-ℓ0is structured to take advantage of massively parallel architectures.