Abstract
The primary challenge in linear inverse problems is to design stable and robust decoders to reconstruct highdimensional vectors from a lowdimensional observation through a linear operator. Sparsity, lowrank, and related assumptions are typically exploited to design decoders, whose performance is then bounded based on some measure of deviation from the idealized model, typically using a norm. This paper focuses on characterizing the fundamental performance limits that can be expected from an ideal decoder given a general model, i.e., a general subset of simple vectors of interest. First, we extend the socalled notion of instance optimality of a decoder to settings where one only wishes to reconstruct some part of the original highdimensional vector from a lowdimensional observation. This covers practical settings, such as medical imaging of a region of interest, or audio source separation, when one is only interested in estimating the contribution of a specific instrument to a musical recording. We define instance optimality relatively to a model much beyond the traditional framework of sparse recovery, and characterize the existence of an instance optimal decoder in terms of joint properties of the model and the considered linear operator. Noiseless and noiserobust settings are both considered. We show somewhat surprisingly that the existence of noiseaware instance optimal decoders for all noise levels implies the existence of a noiseblind decoder. A consequence of our results is that for models that are rich enough to contain an orthonormal basis, the existence of an ℓ 2 /ℓ 2 instance optimal decoder is only possible when the linear operator is not substantially dimensionreducing. This covers wellknown cases (sparse vectors, lowrank matrices) as well as a number of seemingly new situations (structured sparsity and sparse inverse covariance matrices for instance). We exhibit an operatordependent norm which, under a modelspecific generalization of the restricted isometry property, always yields a feasible instance optimality property. This norm can be upper bounded by an atomic norm relative to the considered model.
Original language  English 

Pages (fromto)  7928  7946 
Journal  IEEE Transactions on Information Theory 
Volume  60 
Issue number  12 
DOIs  
Publication status  Published  22 Oct 2014 
Keywords
 linear inverse problems
 instance optimality
 null space property
 restricted isometry property
Fingerprint
Dive into the research topics of 'Fundamental Performance Limits for Ideal Decoders in HighDimensional Linear Inverse Problems'. Together they form a unique fingerprint.Profiles

Michael Davies
 School of Engineering  Jeffrey Collins Chair of Signal Processing
Person: Academic: Research Active