## New RIC Bounds via l_q-minimization with 0

The restricted isometry constants (RICs) play an important role in exact recovery theory of sparse signals via l_q(0

The restricted isometry constants (RICs) play an important role in exact recovery theory of sparse signals via l_q(0

Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

The l1-synthesis and l1-analysis models recover structured signals from their undersampled measurements. The solution of the former model is often a sparse sum of dictionary atoms, and that of the latter model often makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We … Read more

We propose a dynamic programming algorithm for projection onto wavelet tree structures. In contrast to other recently proposed algorithms which only give approximate tree projections for a given sparsity, our algorithm is guaranteed to calculate the projection exactly. We also prove that our algorithm has O(Nk) complexity, where N is the signal dimension and k … Read more

This paper improves bounds for restricted isometry constant (RIC) in compressed sensing. Let \phi be a m*n real matrix and k be a positive integer with k

This paper follows the recent discussion on the sparse solution recovery with quasi-norms Lq; q\in(0,1) when the sensing matrix possesses a Restricted Isometry Constant \delta_{2k} (RIC). Our key tool is an improvement on a version of “the converse of a generalized Cauchy-Schwarz inequality” extended to the setting of quasi-norm. We show that, if \delta_{2k}\le 1/2, … Read more

We consider the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0, 1]. We propose … Read more

We consider a class of optimization problems for sparse signal reconstruction which arise in the field of Compressed Sensing (CS). A plethora of approaches and solvers exist for such problems, for example GPSR, FPC AS, SPGL1, NestA, l1 ls, PDCO to mention a few. CS applications lead to very well conditioned optimization problems and therefore … Read more

In signal acquisition, Toeplitz and circulant matrices are widely used as sensing operators. They correspond to discrete convolutions and are easily or even naturally realized in various applications. For compressive sensing, recent work has used random Toeplitz and circulant sensing matrices and proved their efficiency in theory, by computer simulations, as well as through physical … Read more

Based on the classic augmented Lagrangian multiplier method, we propose, analyze and test an algorithm for solving a class of equality-constrained non-smooth optimization problems (chiefly but not necessarily convex programs) with a particular structure. The algorithm effectively combines an alternating direction technique with a nonmonotone line search to minimize the augmented Lagrangian function at each … Read more