Affordable Access

Access to the full text

Sparse signal recovery using a new class of random matrices

Authors
  • Au-Yeung, Enrico
Type
Published Article
Journal
Advances in Pure and Applied Mathematics
Publisher
De Gruyter
Publication Date
Jan 28, 2017
Volume
8
Issue
2
Pages
79–89
Identifiers
DOI: 10.1515/apam-2016-0039
Source
De Gruyter
Keywords
License
Yellow

Abstract

We propose a new class of random matrices that enables the recovery of signals with sparse representation in a known basis with overwhelmingly high probability. To construct a matrix in this class, we begin with a fixed non-random matrix that satisfies two very general conditions. Then we decompose the matrix into pieces of sparse matrices. A random sum (involving Bernoulli random variables) of these pieces of sparse matrices is used to construct the final matrix. We say that the random matrix is the randomized Bernoulli transform of the original matrix. The random matrix is not created by filling all its entries with random variables, as in the case of Gaussian or Bernoulli matrices. Therefore, as a benefit, far fewer number of random variables are needed to generate this new type of random matrices. We prove that the number of samples needed to recover a random signal is proportional to the sparsity of the signal, up to a logarithmic factor, and hence this number is nearly optimal.

Report this publication

Statistics

Seen <100 times