Abstract | ||
---|---|---|
We have developed an approximate signal recovery algorithm with low
computational cost for compressed sensing on the basis of randomly constructed
sparse measurement matrices. The law of large numbers and the central limit
theorem suggest that the developed algorithm saturates the Donoho-Tanner weak
threshold for the perfect recovery when the matrix becomes as dense as the
signal size $N$ and the number of measurements $M$ tends to infinity keep
$\alpha=M/N \sim O(1)$, which is supported by extensive numerical experiments.
Even when the numbers of non-zero entries per column/row in the measurement
matrices are limited to $O(1)$, numerical experiments indicate that the
algorithm can still typically recover the original signal perfectly with an
$O(N)$ computational cost per update as well if the density $\rho$ of non-zero
entries of the signal is lower than a certain critical value $\rho_{\rm
th}(\alpha)$ as $N,M \to \infty$. |
Year | Venue | Keywords |
---|---|---|
2011 | Clinical Orthopaedics and Related Research | central limit theorem,compressed sensing,sparse matrix,neural network,information theory,law of large numbers,critical value |
Field | DocType | Volume |
Central limit theorem,Matrix (mathematics),Critical value,Signal recovery,Law of large numbers,Compressed sensing,Sparse matrix,Discrete mathematics,Combinatorics,Mathematical optimization,Infinity,Algorithm,Mathematics | Journal | abs/1102.3 |
Citations | PageRank | References |
3 | 0.54 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoshiyuki Kabashima | 1 | 136 | 27.83 |
tadashi | 2 | 92 | 27.26 |