English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the support recovery problem for compressed sensing, where the goalis to reconstruct the a high-dimensional $K$-sparse signal$\mathbf{x}\in\mathbb{R}^N$, from low-dimensional linear measurements with andwithout noise. Our key contribution is a new compressed sensing frameworkthrough a new family of carefully designed sparse measurement matricesassociated with minimal measurement costs and a low-complexity recoveryalgorithm. The measurement matrix in our framework is designed based on thewell-crafted sparsification through capacity-approaching sparse-graph codes,where the sparse coefficients can be recovered efficiently in a few iterationsby performing simple error decoding over the observations. We formally connectthis general recovery problem with sparse-graph decoding in packetcommunication systems, and analyze our framework in terms of the measurementcost, time complexity and recovery performance. In the noiseless setting, ourframework can recover any arbitrary $K$-sparse signal in $O(K)$ time using $2K$measurements asymptotically with high probability. In the noisy setting, whenthe sparse coefficients take values in a finite and quantized alphabet, ourframework can achieve the same goal in time $O(K\log(N/K))$ using$O(K\log(N/K))$ measurements obtained from measurement matrix with elements$\{-1,0,1\}$. When the sparsity $K$ is sub-linear in the signal dimension$K=O(N^\delta)$ for some $0<\delta<1$, our results are order-optimal in termsof measurement costs and run-time, both of which are sub-linear in the signaldimension $N$. The sub-linear measurement cost and run-time can also beachieved with continuous-valued sparse coefficients, with a slight increment inthe logarithmic factors. This offers the desired scalability of our frameworkthat can potentially enable real-time or near-real-time processing for massivedatasets featuring sparsity.

Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes