Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStable Recovery with Analysis Decomposable Priors
72
0
0.0
(
0
)
Added by
Jalal Fadili
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we investigate in a unified way the structural properties of solutions to inverse problems. These solutions are regularized by the generic class of semi-norms defined as a decomposable norm composed with a linear operator, the so-called analysis type decomposable prior. This encompasses several well-known analysis-type regularizations such as the discrete total variation (in any dimension), analysis group-Lasso or the nuclear norm. Our main results establish sufficient conditions under which uniqueness and stability to a bounded noise of the regularized solution are guaranteed. Along the way, we also provide a strong sufficient uniqueness result that is of independent interest and goes beyond the case of decomposable norms.
rate research
Read More
We present a detailed analysis of the unconstrained $ell_1$-method Lasso method for sparse recovery of noisy data. The data is recovered by sensing its compressed output produced by randomly generated class of observing matrices satisfying a Restricted Isometry Property. We derive a new $ell_1$-error estimate which highlights the dependence on a certain compressiblity threshold: once the computed re-scaled residual crosses that threshold, the error is driven only by the (assumed small) noise and compressiblity. Here we identify the re-scaled residual as a key quantity which drives the error and we derive its sharp lower bound of order square-root of the size of the support of the computed solution.
Approximate Message Passing (AMP) has been shown to be an excellent statistical approach to signal inference and compressed sensing problem. The AMP framework provides modularity in the choice of signal prior; here we propose a hierarchical form of the Gauss-Bernouilli prior which utilizes a Restricted Boltzmann Machine (RBM) trained on the signal support to push reconstruction performance beyond that of simple iid priors for signals whose support can be well represented by a trained binary RBM. We present and analyze two methods of RBM factorization and demonstrate how these affect signal reconstruction performance within our proposed algorithm. Finally, using the MNIST handwritten digit dataset, we show experimentally that using an RBM allows AMP to approach oracle-support performance.
Generative neural networks have been empirically found very promising in providing effective structural priors for compressed sensing, since they can be trained to span low-dimensional data manifolds in high-dimensional signal spaces. Despite the non-convexity of the resulting optimization problem, it has also been shown theoretically that, for neural networks with random Gaussian weights, a signal in the range of the network can be efficiently, approximately recovered from a few noisy measurements. However, a major bottleneck of these theoretical guarantees is a network expansivity condition: that each layer of the neural network must be larger than the previous by a logarithmic factor. Our main contribution is to break this strong expansivity assumption, showing that constant expansivity suffices to get efficient recovery algorithms, besides it also being information-theoretically necessary. To overcome the theoretical bottleneck in existing approaches we prove a novel uniform concentration theorem for random functions that might not be Lipschitz but satisfy a relaxed notion which we call pseudo-Lipschitzness. Using this theorem we can show that a matrix concentration inequality known as the Weight Distribution Condition (WDC), which was previously only known to hold for Gaussian matrices with logarithmic aspect ratio, in fact holds for constant aspect ratios too. Since the WDC is a fundamental matrix concentration inequality in the heart of all existing theoretical guarantees on this problem, our tighter bound immediately yields improvements in all known results in the literature on compressed sensing with deep generative priors, including one-bit recovery, phase retrieval, low-rank matrix recovery, and more.
This paper studies the problem of accurately recovering a structured signal from a small number of corrupted sub-Gaussian measurements. We consider three different procedures to reconstruct signal and corruption when different kinds of prior knowledge are available. In each case, we provide conditions (in terms of the number of measurements) for stable signal recovery from structured corruption with added unstructured noise. Our results theoretically demonstrate how to choose the regularization parameters in both partially and fully penalized recovery procedures and shed some light on the relationships among the three procedures. The key ingredient in our analysis is an extended matrix deviation inequality for isotropic sub-Gaussian matrices, which implies a tight lower bound for the restricted singular value of the extended sensing matrix. Numerical experiments are presented to verify our theoretical results.
Because of its self-regularizing nature and uncertainty estimation, the Bayesian approach has achieved excellent recovery performance across a wide range of sparse signal recovery applications. However, most methods are based on the real-value signal model, with the complex-value signal model rarely considered. Typically, the complex signal model is adopted so that phase information can be utilized. Therefore, it is non-trivial to develop Bayesian models for the complex-value signal model. Motivated by the adaptive least absolute shrinkage and selection operator (LASSO) and the sparse Bayesian learning (SBL) framework, a hierarchical model with adaptive Laplace priors is proposed for applications of complex sparse signal recovery in this paper. The proposed hierarchical Bayesian framework is easy to extend for the case of multiple measurement vectors. Moreover, the space alternating principle is integrated into the algorithm to avoid using the matrix inverse operation. In the experimental section of this work, the proposed algorithm is concerned with both complex Gaussian random dictionaries and directions of arrival (DOA) estimations. The experimental results show that the proposed algorithm offers better sparsity recovery performance than the state-of-the-art methods for different types of complex signals.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
