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]

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 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]

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]

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]