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

Much of the existing literature in sparse recovery is concerned with thefollowing question: given a sparsity pattern and a corresponding regularizer,derive conditions on the dictionary under which exact recovery is possible. Inthis paper, we study the opposite question: given a dictionary and the 1-normregularizer, find the largest sparsity pattern that can be recovered. We showthat such a pattern is described by a mathematical object called a "maximumabstract simplicial complex", and provide two different characterizations ofthis object: one based on extreme points and the other based on vectors ofminimal support. In addition, we show how this new framework is useful in thestudy of sparse recovery problems when the dictionary takes the form of a graphincidence matrix or a partial discrete Fourier transform. In case of incidencematrices, we show that the largest sparsity pattern that can be recovered isdetermined by the set of simple cycles of the graph. As a byproduct, we showthat standard sparse recovery can be certified in polynomial time, althoughthis is known to be NP-hard for general matrices. In the case of the partialdiscrete Fourier transform, our characterization of the largest sparsitypattern that can be recovered requires the unknown signal to be real and itsdimension to be a prime number.

What is the Largest Sparsity Pattern that Can Be Recovered by 1-Norm Minimization?