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

The topic of recovery of a structured model given a small number of linearobservations has been well-studied in recent years. Examples include recoveringsparse or group-sparse vectors, low-rank matrices, and the sum of sparse andlow-rank matrices, among others. In various applications in signal processingand machine learning, the model of interest is known to be structured inseveral ways at the same time, for example, a matrix that is simultaneouslysparse and low-rank.  Often norms that promote each individual structure are known, and allow forrecovery using an order-wise optimal number of measurements (e.g., $\ell_1$norm for sparsity, nuclear norm for matrix rank). Hence, it is reasonable tominimize a combination of such norms. We show that, surprisingly, if we usemulti-objective optimization with these norms, then we can do no better,order-wise, than an algorithm that exploits only one of the present structures.This result suggests that to fully exploit the multiple structures, we need anentirely new convex relaxation, i.e. not one that is a function of the convexrelaxations used for each structure. We then specialize our results to the caseof sparse and low-rank matrices. We show that a nonconvex formulation of theproblem can recover the model from very few measurements, which is on the orderof the degrees of freedom of the matrix, whereas the convex problem obtainedfrom a combination of the $\ell_1$ and nuclear norms requires many moremeasurements. This proves an order-wise gap between the performance of theconvex and nonconvex recovery problems in this case. Our framework applies toarbitrary structure-inducing norms as well as to a wide range of measurementensembles. This allows us to give performance bounds for problems such assparse phase retrieval and low-rank tensor completion.

Simultaneously Structured Models with Application to Sparse and Low-rank Matrices