NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
954
Citation
69
Reference
10
Related Paper
Citation Trend
Abstract:
Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. Inspired by recent breakthroughs in the development of novel first-order methods in convex optimization, most notably Nesterov's smoothing technique, this paper introduces a fast and accurate algorithm for solving common recovery problems in signal processing. In the spirit of Nesterov's work, one of the key ideas of this algorithm is a subtle averaging of sequences of iterates, which has been shown to improve the convergence properties of standard gradient-descent algorithms. This paper demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as 1) it is computationally efficient, 2) it is accurate and returns solutions with several correct digits, 3) it is flexible and amenable to many kinds of reconstruction problems, and 4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization, and convex programs seeking to minimize the l1 norm of Wx under constraints, in which W is not diagonal.Keywords:
Smoothing
Code (set theory)
Minification
Compressive sensing is a methodology for the reconstruction of sparse or compressible signals using far fewer samples than required by the Nyquist criterion. However, many of the results in compressive sensing concern random sampling matrices such as Gaussian and Bernoulli matrices. In common physically feasible signal acquisition and reconstruction scenarios such as super-resolution of images, the sensing matrix has a non-random structure with highly correlated columns. Here we present a compressive sensing recovery algorithm that exploits this correlation structure. We provide algorithmic justification as well as empirical comparisons.
SIGNAL (programming language)
Nyquist–Shannon sampling theorem
Nyquist rate
Matrix (chemical analysis)
Signal reconstruction
Cite
Citations (0)
Compressed Sensing is a new sampling theorem,it points out that if a signal can be compressed under some conditions,that a very accurate reconstruction can be obtained from a relatively small number of non-traditional samples.On the basis of compressed sensing,the paper presents multiscale compressed sensing.The numerical experiments demonstrate that multiscale compressed sensing can give better quality reconstruction than a literal deployment of the compressed sensing methodology.
Signal reconstruction
SIGNAL (programming language)
Cite
Citations (0)
This paper presents a novel approach, compressive mobile sensing, to use mobile sensors to sample and reconstruct sensing fields based on compressive sensing. Compressive sensing is an emerging research field based on the fact that a small number of linear measurements can recover a sparse signal without losing any useful information. Using compressive sensing, the signal can be recovered by a sampling rate that is much lower than the requirements from the well-known Shannon sampling theory. The proposed compressive mobile sensing approach has not only the merits of compressive sensing, but also the flexibility of different sampling densities for areas of different interests. A special measurement process makes it different from normal compressive sensing. Adopting importance sampling, compressive mobile sensing enables mobile sensors to move adaptively and acquire more samples from more important areas. A motion planning algorithm is designed based on the result of sparsity analysis to locate areas of more interests. At last, experimental results of 2-D mapping are presented as an implementation compressive mobile sensing.
SIGNAL (programming language)
Cite
Citations (5)
Quantitative evaluations of the noise reduction and signal deformation that are produced in parabolic smoothing are obtained, and their utilization for the optimization of smoothing is discussed. These results ensue from a general method of analysis of smoothing procedures that was developed in a previous paper. As a by-product a new smoothing method is developed. It has practically the same properties as the parabolic one, but smoothing is achieved with a notable reduction in the number of operations required.
Smoothing
Cite
Citations (5)
Recent work in compressed sensing theory shows that m×n independent and identically distributed sensing matrices whose entries are drawn independently from certain probability distributions guarantee exact recovery of a sparse signal with high probability even if m≪n. In particular, it is well understood that the L1 minimization algorithm is able to recover sparse signals from incomplete measurements. In this paper, we propose a novel sparse signal reconstruction method that is based on the reweighted L1 minimization via support recovery.
Minification
Signal Recovery
Signal reconstruction
SIGNAL (programming language)
Cite
Citations (3)
Compressed sensing theory provides a new approach to acquire data as a sampling technique and makes sure that an original sparse signal can be reconstructed from few measurements. The construction of compressed sensing matrices is a central problem in compressed sensing theory. In this paper, the deterministic compressed sensing matrices with characters of finite fields are constructed and the coherence of the matrices are computed. Furthermore, the maximum sparsity of recovering the original sparse signals by using our compressed sensing matrices is obtained. Meanwhile, a comparison is made with the compressed sensing matrices constructed by DeVore based on polynomials over finite fields. In the numerical simulations, our compressed sensing matrix outperforms DeVore’s matrix in the process of recovering original sparse signals.
Mutual coherence
Matrix (chemical analysis)
SIGNAL (programming language)
Restricted isometry property
Cite
Citations (0)
An analysis is made of the effect, in smoothing observational data with a digital computer, of using two smoothing steps, the first having a high data handling rate and a short smoothing time, the second a low data handling rate and a long smoothing time. The analysis shows that for the most commonly used types of smoothing, the effect of the two smoothing operations in series is essentially equivalent to that of a single operation combining the most desirable features of each of the two, i.e., the high data handling rate of the first operation and the long smoothing time of the second. This fact is important in certain control applications where the combination of both these features in one smoother is not possible.
Smoothing
Cite
Citations (4)
Smoothing
Cite
Citations (1)
Surface smoothing is one of the important technologies of reverse engineering. This paper introduces a set of simple and useful algorithms for surface smoothing, including disposing error points, step smoothing, hand smoothing and automation smoothing, relationships among these algorithms and skills of using these algorithms in engineering are discussed in detailed. The feasibility of these algorithms are verified by their application in automobile engineering.
Smoothing
Reverse engineering
Cite
Citations (0)
In this paper, we propose a mesh smoothing method for mesh models with noise. The proposed method enables not only the removal of noise from the vertexes but the preservation and smoothing of shape recognized as edges and comers. The magnitude ratio of 2D area and 3D volume in mesh data is adopted for the smoothing of noise. Comparing with previous smoothing methods, this method does not need many iteration of the smoothing process and could preserve the shape of original model. Experimental results demonstrate improved performance of the proposed approach in 3D mesh smoothing.
Smoothing
Laplacian smoothing
Edge-preserving smoothing
Cite
Citations (0)