On the Effective Measure of Dimension in the Analysis Cosparse Model

DOI10.1109/TIT.2015.2466597zbMATH Open1359.94032arXiv1410.0989OpenAlexW2962896970MaRDI QIDQ2977253FDOQ2977253

Authors: Raja Giryes, Y. Plan, Roman Vershynin 

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Many applications have benefited remarkably from low-dimensional models in the recent decade. The fact that many signals, though high dimensional, are intrinsically low dimensional has given the possibility to recover them stably from a relatively small number of their measurements. For example, in compressed sensing with the standard (synthesis) sparsity prior and in matrix completion, the number of measurements needed is proportional (up to a logarithmic factor) to the signal's manifold dimension. Recently, a new natural low-dimensional signal model has been proposed: the cosparse analysis prior. In the noiseless case, it is possible to recover signals from this model, using a combinatorial search, from a number of measurements proportional to the signal's manifold dimension. However, if we ask for stability to noise or an efficient (polynomial complexity) solver, all the existing results demand a number of measurements which is far removed from the manifold dimension, sometimes far greater. Thus, it is natural to ask whether this gap is a deficiency of the theory and the solvers, or if there exists a real barrier in recovering the cosparse signals by relying only on their manifold dimension. Is there an algorithm which, in the presence of noise, can accurately recover a cosparse signal from a number of measurements proportional to the manifold dimension? In this work, we prove that there is no such algorithm. Further, we show through numerical simulations that even in the noiseless case convex relaxations fail when the number of measurements is comparable to the manifold dimension. This gives a practical counter-example to the growing literature on compressed acquisition of signals based on manifold dimension.

Full work available at URL: https://arxiv.org/abs/1410.0989

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Cited In (7)

• Modeling the connection between primary and metastatic tumors
• Pattern formation in a flux limited reaction-diffusion equation of porous media type
• \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
• A general reaction-diffusion model of acidity in cancer invasion
• Compressive sensing with redundant dictionaries and structured measurements
• Image reconstruction using analysis model prior
• A multiscale mathematical model of tumour invasive growth

This page was built for publication: On the Effective Measure of Dimension in the Analysis Cosparse Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977253)