Search

We prove the Johnson-Lindenstrauss property for matrices ΦDξ, where Φ has the restricted isometry property and Dξ is a diagonal matrix containing the entries of a Kronecker product ξ=ξ(1)⊕...⊕ξ(d) of d independent Rademacher vectors. Such embeddings have been proposed in recent works for a number of applications concerning compression of tensor structured data, including the oblivious sketching procedure by Ahle et al. for approximate tensor computations. For preserving the norms of p points simultaneously, our result requires Φ to have the restricted isometry property for sparsity C(d)(logp)d. In the case of subsampled Hadamard matrices, this can improve the dependence of the embedding dimension on p to (logp)d while the best previously known result required (logp)d+1. That is, for the case of d=2 at the core of the oblivious sketching procedure by Ahle et al., the scaling improves from cubic to quadratic. We provide a counterexample to prove that the scaling established in our result is optimal under mild assumptions. [ABSTRACT FROM AUTHOR]

Transformed L1 (TL1) regularization has been shown to have comparable signal recovery capability with L1 L2 regularization and L1/L2 regularization, regardless of whether the measurement matrix satisfies the restricted isometry property (RIP). In the spirit of the TL1 method, we introduce a transformed total variation (TTV) minimization model to investigate robust image recovery from a certain number of noisy measurements by the proposed TTV minimization model in this paper. An optimal error bound, up to a logarithmic factor, of robust image recovery from compressed measurements via the TTV minimization model is established, and the RIP based condition is improved compared with total variation (TV) minimization. Numerical results of image reconstruction demonstrate our theoretical results and illustrate the efficiency of the TTV minimization model among state-of-the-art methods. Empirically, the error bound between the reconstructed image and the original image is shown to be better than that produced by TV minimization. [ABSTRACT FROM AUTHOR]

The l1-l2 regularization is a popular nonconvex yet Lipschitz continuous metric, which has been widely used in signal and image processing. The theory for the l1-l2 minimization method shows that it has superior sparse recovery performance over the classical l1 minimization method. The motivation and major contribution of this paper is to provide a positive answer to the open problem posed in [T.-H. Ma, Y. Lou, and T.-Z. Huang, SIAM J. Imaging Sci., 10 (2017), pp. 1346-1380] about the sufficient conditions that can be sharpened for the l1-l2 minimization method. The novel technique used in our analysis of the l1-l2 minimization method is a crucial sparse representation adapted to the l1-l2 metric which is different from the other state-of-the-art works in the context of the l1-l2 minimization method. The new restricted isometry property (RIP) analysis is better than the existing RIP based conditions to guarantee the exact and stable recovery of signals. [ABSTRACT FROM AUTHOR]

An important observation in compressed sensing is that the 0 minimizer of an underdetermined linear system is equal to the 1 minimizer when there exists a sparse solution vector and a certain restricted isometry property holds. Here, we develop a continuous analogue of this observation and show that the best L0 and L1 polynomial approximants of a polynomial that is corrupted on a set of small measure are nearly equal. We demonstrate an error localization property of best L1 polynomial approximants and use our observations to develop an improved algorithm for computing best L1 polynomial approximants to continuous functions. [ABSTRACT FROM AUTHOR]

The simulations indicate that the existing hard thresholding technique independent of the residual function may cause a dramatic increase or numerical oscillation of the residual. This inherent drawback of the hard thresholding renders the traditional thresholding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop a truly efficient thresholding method is a fundamental question in this field. The aim of this paper is to address this question by proposing a new thresholding technique based on the notion of optimal k-thresholding. The central idea for this new development is to connect the k-thresholding directly to the residual reduction during the course of algorithms. This leads to a natural design principle for the efficient thresholding methods. Under the restricted isometry property, we prove that the optimal thresholding based algorithms are globally convergent to the solution of sparse optimization problems. The numerical experiments demonstrate that when solving sparse optimization problems, the traditional hard thresholding methods have been significantly transcended by the proposed algorithms which can even outperform the classic `1-minimization method in many situations. [ABSTRACT FROM AUTHOR]

This paper deals with tensor completion for the solution of multidimensional inverse problems arising in nuclear magnetic resonance (NMR) relaxometry. We study the problem of reconstructing an approximately low-rank tensor from a small number of noisy linear measurements. New recovery guarantees, numerical algorithms, nonuniform sampling strategies, and parameter selection methods are developed in this context. In particular, we derive a fixed point continuation algorithm for tensor completion and prove its convergence. A restricted isometry property-based tensor recovery guarantee is proved. Probabilistic recovery guarantees are obtained for sub-Gaussian measurement operators and for measurements obtained by nonuniform sampling from a Parseval tight frame. The proposed algorithm is then applied to the setting of nuclear magnetic resonance relaxometry, for both simulated and experimental data. We compare our results with basis pursuit as well as with the state-of-the-art nonsubsampled data acquisition and reconstruction approach. Our experiments indicate that tensor recovery promises to significantly accelerate N-dimensional NMR relaxometry and related experiments, enabling previously impractical experiments to be performed. Our methods could also be applied to other similar inverse problems arising in machine learning, signal and image processing, and computer vision. [ABSTRACT FROM AUTHOR]

This paper concerns itself with the rank regularized minimization problem with a spectral norm ball constraint. We reformulate this NP-hard problem as an equivalent MPGCC (mathematical program with a generalized complementarity constraint) and show that the penalty problem, yielded by moving the generalized complementarity constraint to the objective, is exact in the sense that it has the same global optimal solution set as the MPGCC does when the penalty parameter is over a threshold. Then, by solving the exact penalty problem in an alternating way, we propose a multistage convex relaxation approach, and provide its theoretical guarantee for the rank regularized least squares problem with a spectral norm ball constraint. Specifically, we derive the error and approximate rank bounds for the optimal solution of each stage and quantify the reduction of the error and approximate rank bounds of the first stage convex relaxation (which is exactly the nuclear norm relaxation) in the subsequent stages. In particular, we establish the geometric convergence in a statistical sense for the error sequence, which reduces to the linear convergence in the noiseless case and implies the exact recoverability of the multistage convex relaxation approach. Numerical experiments are conducted on some low-rank matrix recovery examples to confirm the theoretical results. [ABSTRACT FROM AUTHOR]

We study a truncated difference of l1 and l2 norms as a nonconvex metric for recovering sparse vectors and low-rank matrices from linear measurements. By discarding large magnitude entries/singular values in penalization, the proposed metric, denoted as truncated l1-2, achieves a nearly unbiased approximation of the vector sparsity/matrix rank. We establish exact and stable recovery conditions of truncated l1-2 minimization under the restricted isometry property (RIP) framework. Computationally, we apply the difference of convex functions algorithm (DCA) to efficiently solve truncated l1-2 minimization with guaranteed convergence. Our method is validated on sparse vector recovery, matrix completion, and magnetic resonance imaging (MRI) reconstruction, with performance com- parable to the state of the art. Particularly for MRI reconstruction, it succeeds in reconstructing the 256 × 256 Shepp{Logan phantom image from merely 7 radial lines. [ABSTRACT FROM AUTHOR]

The purpose of this paper is twofold. The first is to point out that the property of uniform recovery, meaning that all sparse vectors are recovered, does not hold in many applications where compressed sensing is successfully used. This includes fields like magnetic resonance imaging (MRI), nuclear magnetic resonance computerized tomography, electron tomography, radio interferometry, helium atom scattering, and uorescence microscopy. We demonstrate that for natural compressed sensing matrices involving a level based reconstruction basis (e.g., wavelets), the number of measurements required to recover all s-sparse signals for reasonable s is excessive. In particular, uniform recovery of all s-sparse signals is quite unrealistic. This realization explains why the restricted isometry property (RIP) is insufficient for explaining the success of compressed sensing in various practical applications. The second purpose of the paper is to introduce a new framework based on a generalized RIP and a generalized nullspace property that fit the applications where compressed sensing is used. We demonstrate that the shortcomings previously used to prove that uniform recovery is unreasonable no longer apply if we instead ask for structured recovery that is uniform only within each of the levels. To examine this phenomenon, a new tool, termed the \restricted isometry property in levels" (RIPL) is described and analyzed. Furthermore, we show that with certain conditions on the RIPL, a form of uniform recovery within each level is possible. Fortunately, recent theoretical advances made by Li and Adcock demonstrate the existence of large classes of matrices that satisfy the RIPL. Moreover, such matrices are used extensively in applications such as MRI. Finally, we conclude the paper by providing examples that demonstrate the optimality of the results obtained. [ABSTRACT FROM AUTHOR]

Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary D. This problem is now understood to be well-posed and efficiently solvable under suitable assumptions on the measurements and dictionary if the number of measurements scales roughly with the sparsity level. One sufficient condition for such is the D-restricted isometry property (D-RIP), which asks that the sampling matrix approximately preserve the norm of all signals which are sufficiently sparse in D. While many classes of random matrices are known to satisfy such conditions, such matrices are not representative of the structural constraints imposed by practical sensing systems. We close this gap in the theory by demonstrating that one can subsample a fixed orthogonal matrix in such a way that the D-RIP will hold, provided this basis is sufficiently incoherent with the sparsifying dictionary D. We also extend this analysis to allow for weighted sparse expansions. Consequently, we arrive at compressive sensing recovery guarantees for structured measurements and redundant dictionaries, opening the door to a wide array of practical applications. [ABSTRACT FROM AUTHOR]

Inspired by significant real-life applications, particularly sparse phase retrieval and sparse pulsation frequency detection in asteroseismology, we investigate a general framework for compressed sensing, where the measurements are quasi-linear. We formulate natural generalizations of the well-known restricted isometry property (RIP) toward nonlinear measurements, which allow us to prove both unique identifiability of sparse signals as well as the convergence of recovery algorithms to compute them efficiently. We show that for certain randomized quasi-linear measurements, including Lipschitz perturbations of classical RIP matrices and phase retrieval from random projections, the proposed restricted isometry properties hold with high probability. We analyze a generalized orthogonal least squares (OLS) under the assumption that magnitudes of signal entries to be recovered decay quickly. Greed is good again, as we show that this algorithm performs efficiently in phase retrieval and asteroseismology. For situations where the decay assumption on the signal does not necessarily hold, we propose two alternative algorithms, which are natural generalizations of the well-known iterative hard- and soft-thresholding. While these algorithms are rarely successful for the mentioned applications, we show their strong recovery guarantees for quasi-linear measurements which are Lipschitz perturbations of RIP matrices. [ABSTRACT FROM AUTHOR]

This article offers an accessible but rigorous and essentially self-contained account of some of the central ideas in compressed sensing, aimed at nonspecialists and undergraduates who have had linear algebra and some probability. The basic premise is first illustrated by considering the problem of detecting a few defective items in a large set. We then build up the mathematical framework of compressed sensing to show how combining efficient sampling methods with elementary ideas from linear algebra and a bit of approximation theory, optimization, and probability allows the estimation of unknown quantities with far less sampling of data than traditional methods. [ABSTRACT FROM AUTHOR]

This paper presents near-optimal guarantees for stable and robust image recovery from undersam-pled noisy measurements using total variation minimization. In particular, we show that from O(s log (N)) nonadaptive linear measurements, an image can be reconstructed to within the best s-term approximation of its gradient up to a logarithmic factor, and this factor can be removed by taking slightly more measurements. Along the way, we prove a strengthened Sobolev inequality for functions lying in the null space of a suitably incoherent matrix. [ABSTRACT FROM AUTHOR]

Consider an m x N matrix Φ with the restricted isometry property of order k and level δ; that is, the norm of any k-sparse vector in ℝN is preserved to within a multiplicative factor of 1 ± δ under application of Φ. We show that by randomizing the column signs of such a matrix Φ, the resulting map with high probability embeds any fixed set of p = O(ek) points in ℝN into ℝm without distorting the norm of any point in the set by more than a factor of 1 ± 4δ. Consequently, matrices with the restricted isometry property and with randomized column signs provide optimal Johnson-Lindenstrauss embeddings up to logarithmic factors in N. In particular, our results improve the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices; for partial Fourier and partial Hadamard matrices, we improve the recent bound m ≳ δ-4 log (p) log4 (N) given by Ailon and Liberty to m ≳ δ-2 log(p) log4; (N), which is optimal up to the logarithmic factors in N. Our results also have a direct application in the area of compressed sensing for redundant dictionaries. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS) seeks to recover an unknown vector with N entries by making far fewer than N measurements; it posits that the number of CS measurements should be comparable to the information content of tile vector, not simply N. CS combines directly the important task of compression with the measurement task. Since its introduction in 2004 there have been hundreds of papers on CS, a large fraction of which develop algorithms to recover a signal from its compressed measurements. Because of the paradoxical nature of CS--exact reconstruction from seemingly undersampled measurements--it is crucial for acceptance of an algorithm that rigorous analyses verify the degree of undersampling the algorithm permits. The restricted isometry property (RIP) has become the dominant tool used for the analysis in such cases. We present here an asymmetric form of RIP that gives tighter bounds than the usual symmetric one. We give the best known bounds on the RIP constants for matrices from the Gaussian ensemble. Our derivations illustrate the way in which the combinatorial nature of CS is controlled. Our quantitative bounds on the RIP allow precise statements as to how aggressively a signal can be undersampled, the essential question for practitioners. We also document the extent to which RIP gives precise information about the true performance limits of CS, by comparison with approaches from high-dimensional geometry. [ABSTRACT FROM AUTHOR]