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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we propose new efficient algorithms to verify the null spacecondition in compressed sensing (CS). Given an $(n-m) \times n$ ($m>0$) CSmatrix $A$ and a positive $k$, we are interested in computing $\displaystyle\alpha_k = \max_{\{z: Az=0,z\neq 0\}}\max_{\{K: |K|\leq k\}}$ ${\|z_K\|_{1}}{\|z\|_{1}}$, where $K$ represents subsets of $\{1,2,...,n\}$, and $|K|$is the cardinality of $K$. In particular, we are interested in finding themaximum $k$ such that $\alpha_k < {1}{2}$. However, computing $\alpha_k$ isknown to be extremely challenging. In this paper, we first propose a series ofnew polynomial-time algorithms to compute upper bounds on $\alpha_k$. Based onthese new polynomial-time algorithms, we further design a new sandwichingalgorithm, to compute the \emph{exact} $\alpha_k$ with greatly reducedcomplexity. When needed, this new sandwiching algorithm also achieves a smoothtradeoff between computational complexity and result accuracy. Empiricalresults show the performance improvements of our algorithm over existing knownmethods; and our algorithm outputs precise values of $\alpha_k$, with muchlower complexity than exhaustive search.

Precisely Verifying the Null Space Conditions in Compressed Sensing: A Sandwiching Algorithm