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]