Search

This paper introduces a nonconvex ℓ1−2-analysis model: minx(∥D∗x∥ 1 −∥D∗x∥ 2)s.t. Ax = y, where A is a measurement matrix and D is a tight frame. Our main motivation is to generalize the sparse recovery via ℓ1 − ℓ2 minimization to this new model. As a nonconvex model, it is well known that its global minimizer and local minimizer are usually inconsistent. This paper provides a type of null space property (NSP) characterization which are necessary and sufficient conditions for the measurement matrix A such that a vector x can be recovered from Ax with a tight frame D via ℓ1−2-analysis local minimization, or any vector x can be uniformly recovered from Ax with a tight frame D via ℓ1−2-analysis minimization locally and globally. [ABSTRACT FROM AUTHOR]

This paper concentrates on the recovery of block-sparse signals, which are not only sparse but also nonzero elements are arrayed into some blocks (clusters) rather than being arbitrary distributed all over the vector, from linear measurements. We establish high-order sufficient conditions based on block RIP, which could ensure the exact recovery of every block s-sparse signal in the noiseless case via mixed l 2 / l p {l_{2}/l_{p}} minimization method, and the stable and robust recovery in the case that signals are not accurately block-sparse in the presence of noise. Additionally, a lower bound on necessary number of random Gaussian measurements is gained for the condition to be true with overwhelming probability. Furthermore, a series of numerical experiments are conducted to demonstrate the performance of the mixed l 2 / l p {l_{2}/l_{p}} minimization. To the best of the authors’ knowledge, the recovery guarantees established in this paper are superior to those currently available. [ABSTRACT FROM AUTHOR]

This study aims to reconstruct signals that are sparse with a tight frame from undersampled data by using the ℓ q -minimization method. This problem can be cast as a ℓ q -minimization problem with a tight frame subjected to an undersampled measurement with a known noise bound. We proved that if the measurement matrix satisfies the restricted isometry property with δ 2 s ≤ 1 / 2 , there exists a value q 0 such that for any q ∈ (0 , q 0 ] , any signal that is s-sparse with a tight frame can be robustly recovered to the true signal. We estimated q 0 as q 0 = 2 / 3 in the case of δ 2 s ≤ 1 / 2 and discussed that the value of q 0 can be much higher. We also showed that when δ 2 s ≤ 0.3317 , for any q ∈ (0 , 1 ] , robust recovery for signals via ℓ q -minimization holds, which is consistent with the case of ℓ q -minimization without a tight frame. [ABSTRACT FROM AUTHOR]

Expressing a matrix as the sum of a low-rank matrix plus a sparse matrix is a flexible model capturing global and local features in data. This model is the foundation of robust principle component analysis [1,2] , and popularized by dynamic-foreground/static-background separation [3]. Compressed sensing, matrix completion, and their variants [4,5] have established that data satisfying low complexity models can be efficiently measured and recovered from a number of measurements proportional to the model complexity rather than the ambient dimension. This manuscript develops similar guarantees showing that m × n matrices that can be expressed as the sum of a rank- r matrix and a s -sparse matrix can be recovered by computationally tractable methods from O (r (m + n − r) + s) log ⁡ (m n / s) linear measurements. More specifically, we establish that the low-rank plus sparse matrix set is closed provided the incoherence of the low-rank component is upper bounded as μ < m n / (r s) , and subsequently, the restricted isometry constants for the aforementioned matrices remain bounded independent of problem size provided p / m n , s / p , and r (m + n − r) / p remain fixed. Additionally, we show that semidefinite programming and two non-convex hard threshold gradient descent algorithms, NIHT and NAHT, converge to the measured matrix provided the measurement operator's RICs are sufficiently small. These results also provably solve the convex formulation of Robust PCA with the asymptotically optimal fraction of corruptions α = O (1 / (μ r)) , where s = α 2 m n , and improve the previously known guarantees by not requiring that the fraction of corruptions is spread in every column and row by being upper bounded with α. Numerical experiments illustrating these results are shown for synthetic problems, dynamic-foreground/static-background separation, and multispectral imaging. [ABSTRACT FROM AUTHOR]

We investigate the problems of reconstruction signals' distinct subcomponents, that are approximately sparse in terms of morphologically different dictionaries, from a few noisy linear measurements. We show that under common assumptions on a restricted isometric property adapted to the composed dictionary and a mutual coherence condition between the two different dictionaries, the two distinct subcomponents can be stably and approximately recovered via the unconstrained l 1 -split analysis, with an error bound that is in general unimprovable for the Gaussian noises. [ABSTRACT FROM AUTHOR]

We propose the Group Orthogonal Matching Pursuit (GOMP) algorithm to recover group sparse signals from noisy measurements. Under the group restricted isometry property (GRIP), we prove the instance optimality of the GOMP algorithm for any decomposable approximation norm. Meanwhile, we show the robustness of the GOMP under the measurement error. Compared with the P-norm minimization approach, the GOMP is easier to implement, and the assumption of γ -decomposability is not required. The simulation results show that the GOMP is very efficient for group sparse signal recovery and significantly outperforms Basis Pursuit in both scalability and solution quality. [ABSTRACT FROM AUTHOR]

Compressive learning forms the exciting intersection between compressed sensing and statistical learning where one exploits sparsity of the learning model to reduce the memory and/or computational complexity of the algorithms used to solve the learning task. In this paper, we look at the independent component analysis (ICA) model through the compressive learning lens. In particular, we show that solutions to the cumulant-based ICA model have a particular structure that induces a low-dimensional model set that resides in the cumulant tensor space. By showing that a restricted isometry property holds for random cumulants e.g. Gaussian ensembles, we prove the existence of a compressive ICA scheme. Thereafter, we propose two algorithms of the form of an iterative projection gradient and an alternating steepest descent algorithm for compressive ICA, where the order of compression asserted from the restricted isometry property is realized through empirical results. We provide analysis of the CICA algorithms including the effects of finite samples. The effects of compression are characterized by a trade-off between the sketch size and the statistical efficiency of the ICA estimates. By considering synthetic and real datasets, we show the substantial memory gains achieved over well-known ICA algorithms by using one of the proposed CICA algorithms. [ABSTRACT FROM AUTHOR]

Previous work regarding low-rank matrix recovery has concentrated on the scenarios in which the matrix is noise-free and the measurements are corrupted by noise. However, in practical application, the matrix itself is usually perturbed by random noise preceding to measurement. This paper concisely investigates this scenario and evidences that, for most measurement schemes utilized in compressed sensing, the two models are equivalent with the central distinctness that the noise associated with double noise model is larger by a factor to m n / M , where m , n are the dimensions of the matrix and M is the number of measurements. Additionally, this paper discusses the reconstruction of low-rank matrices in the setting, presents sufficient conditions based on the associating null space property to guarantee the robust recovery and obtains the number of measurements. Furthermore, for the non-Gaussian noise scenario, we further explore it and give the corresponding result. The simulation experiments conducted, on the one hand show effect of noise variance on recovery performance, on the other hand demonstrate the verifiability of the proposed model. [ABSTRACT FROM AUTHOR]

Leveraging recent advances in additive combinatorics, we exhibit explicit matrices satisfying the Restricted Isometry Property with better parameters. Namely, for ε = 3.26 · 10 - 7 , large k and k 2 - ε ≤ N ≤ k 2 + ε , we construct n × N RIP matrices of order k with k = Ω (n 1 / 2 + ε / 4) . [ABSTRACT FROM AUTHOR]

We provide novel sufficient conditions for the uniform recovery of sparse Legendre expansions using ℓ1 minimization, where the sampling points are drawn according to orthogonalization (uniform) measure. So far, conditions of the form m≳Θ2s×logfactors have been relied on to determine the minimum number of samples m that guarantees successful reconstruction of s‐sparse vectors when the measurement matrix is associated to an orthonormal system. However, in case of sparse Legendre expansions, the uniform bound Θ of Legendre systems is so high that these conditions are unable to provide meaningful guarantees. In this paper, we present an analysis which employs the envelop bound of all Legendre polynomials instead, and prove a new recovery guarantee for s‐sparse Legendre expansions, m≳s2×logfactors, which is independent of Θ. Arguably, this is the first recovery condition established for orthonormal systems without assuming the uniform boundedness of the sampling matrix. The key ingredient of our analysis is an extension of chaining arguments, recently developed in Bourgain and Chkifa et al., to handle the envelope bound. Furthermore, our recovery condition is proved via restricted eigenvalue property, a less demanding replacement of restricted isometry property which is perfectly suited to the considered scenario. Along the way, we derive simple criteria to detect good sample sets. Our numerical tests show that sets of uniformly sampled points that meet these criteria will perform better recovery on average. [ABSTRACT FROM AUTHOR]

One of the crucial challenges in applying the theory of compressed sensing in practice is to cope with the perturbation caused by different types of unknown noise, which may arise from the physical implementation or the human mis-modeling. In this paper, we study the robust recovery from a completely perturbed model via a recently popular L 1 - 2 method. By using the powerful restricted isometry constant of order t ⁢ k for t > 1 , we first obtain a series of perturbation analysis results for this L 1 - 2 method, which shows that this method is also able to guarantee a robust recovery for any (nearly) sparse signals when both the ideal observations and the exact measurement matrix are perturbed by the unknown noise. Moreover, one of the established recovery conditions under the noise-free settings is also demonstrated to be much better than the state-of-the-art one. Finally, some simulation experiments are further carried out to verify the effectiveness of this L 1 - 2 method. [ABSTRACT FROM AUTHOR]

This paper studies a kind of weighted l 1 -minimization that is motivated by function interpolation. Combining with the weighted robust null space property, we first propose a new sufficient condition for robust recovery via the weighted l 1 -minimization when the measurements are corrupted by arbitrary noise without requiring the proper estimation of noise level. Second, we investigate the instance optimality of the weighted l 1 -minimization decoder according to the weighted quotient property and the weighted restricted isometry property (RIP). In addition, to give a better error estimation in a general problem to recover noisy compressible signals, we improve the ω -RIP constant δ ω , 3 s from 1 / 3 to (1 7 − 1) / 8 by using the weighted sparsity and Stechkin-type estimate. Our results show that the weighted l 1 -minimization remains not only stable but also robust to reconstruct signals with noisy observations. [ABSTRACT FROM AUTHOR]

Group-sparsity is a common low-complexity signal model with widespread application across various domains of science and engineering. The recovery of such signal ensembles from compressive measurements has been extensively studied in the literature under the assumption that measurement operators are modeled as densely populated random matrices. In this paper, we turn our attention to an acquisition model intended to ease the energy consumption of sensing devices by splitting the measurements up into distinct signal blocks. More precisely, we present uniform guarantees for group-sparse signal recovery in the scenario where a number of sensors obtain independent partial signal observations modeled by block diagonal measurement matrices. We establish a group-sparse variant of the classical restricted isometry property (RIP) for block diagonal sensing matrices acting on group-sparse vectors, and provide conditions under which subgaussian block diagonal random matrices satisfy this group-RIP with high probability. Two different scenarios are considered in particular. In the first scenario, we assume that each sensor is equipped with an independently drawn measurement matrix. We later lift this requirement by considering measurement matrices with constant block diagonal entries. In other words, every sensor is equipped with a copy of the same prototype matrix. The problem of establishing the group-RIP is cast into a form in which one needs to establish the concentration behavior of the suprema of chaos processes which involves estimating Talagrand's γ 2 functional. As a side effect of the proof, we present an extension to Maurey's empirical method to provide new bounds on the covering number of sets consisting of finite convex combinations of possibly infinite sets. [ABSTRACT FROM AUTHOR]

In this paper, the robustness of the orthogonal matching pursuit (OMP) algorithm for multiple measurement vector (MMV) problem under the restricted isometry property (RIP) is presented. Moreover, it is shown that the OMP algorithm can exactly recover K‐row sparse matrices in K iterations under the RIP condition we have presented. Furthermore, the condition is sharp. [ABSTRACT FROM AUTHOR]

The goal of phaseless compressed sensing is to recover an unknown sparse or approximately sparse signal from the magnitude of its measurements. However, it does not take advantage of any support information of the original signal. Therefore, our main contribution in this paper is to extend the theoretical framework for phaseless compressed sensing to incorporate with prior knowledge of the support structure of the signal. Specifically, we investigate two conditions that guarantee stable recovery of a weighted k‐sparse signal via weighted l1 minimization without any phase information. We first prove that the weighted null space property (WNSP) is a sufficient and necessary condition for the success of weighted l1 minimization for weighted k‐sparse phase retrievable. Moreover, we show that if a measurement matrix satisfies the strong weighted restricted isometry property (SWRIP), then the original signal can be stably recovered from the phaseless measurements. [ABSTRACT FROM AUTHOR]

Compressed sensing studies linear recovery problems under structure assumptions. We introduce a new class of measurement operators, coined hierarchical measurement operators, and prove results guaranteeing the efficient, stable and robust recovery of hierarchically structured signals from such measurements. We derive bounds on their hierarchical restricted isometry properties based on the restricted isometry constants of their constituent matrices, generalizing and extending prior work on Kronecker-product measurements. As an exemplary application, we apply the theory to two communication scenarios. The fast and scalable HiHTP algorithm is shown to be suitable for solving these types of problems and its performance is evaluated numerically in terms of sparse signal recovery and block detection capability. [ABSTRACT FROM AUTHOR]

In this paper, we study compressed data separation (CDS) problem, i.e., sparse data separation from a few linear random measurements. We propose the nonconvex ℓq-split analysis with ℓ∞-constraint and 0 < q ≤ 1. We call the algorithm ℓq-split-analysis Dantzig selector (ℓq-split-analysis DS). We show that the two distinct subcomponents that are approximately sparse in terms of two different dictionaries could be stably approximated via the ℓq-split-analysis DS, provided that the measurement matrix satisfies either a classical D-RIP (Restricted Isometry Property with respect to Dictionaries and ℓ2 norm) or a relatively new (D, q)-RIP (RIP with respect to Dictionaries and ℓq-quasi norm) condition and the two different dictionaries satisfy a mutual coherence condition between them. For the Gaussian random measurements, the measurement number needed for the (D, q)-RIP condition is far less than those needed for the D-RIP condition and the (D, 1)-RIP condition when q is small enough. [ABSTRACT FROM AUTHOR]

In compressed sensing, the restricted isometry property (RIP) on $M \times N$ sensing matrices (where $M < N$) guarantees efficient reconstruction of sparse vectors. A matrix has the $(s,\delta)$ - $\mathsf {RIP}$ property if behaves as a $\delta $ -approximate isometry on $s$ -sparse vectors. It is well known that an $M\times N$ matrix with i.i.d. $\mathcal {N}(0,1/M)$ entries is $(s,\delta)$ - $\mathsf {RIP}$ with high probability as long as $s\lesssim \delta ^{2}~M/\log N$. On the other hand, most prior works aiming to deterministically construct $(s,\delta)$ - $\mathsf {RIP}$ matrices have failed when $s \gg \sqrt {M}$. An alternative way to find an RIP matrix could be to draw a random gaussian matrix and certify that it is indeed RIP. However, there is evidence that this certification task is computationally hard when $s \gg \sqrt {M}$ , both in the worst case and the average case. In this paper, we investigate the exact average-case time complexity of certifying the RIP property for $M\times N$ matrices with i.i.d. $\mathcal {N}(0,1/M)$ entries, in the “possible but hard” regime $\sqrt {M} \ll s\lesssim M/\log N$. Based on analysis of the low-degree likelihood ratio, we give rigorous evidence that subexponential runtime $N^{\tilde \Omega (s^{2}/M)}$ is required, demonstrating a smooth tradeoff between the maximum tolerated sparsity and the required computational power. This lower bound is essentially tight, matching the runtime of an existing algorithm due to Koiran and Zouzias. Our hardness result allows $\delta $ to take any constant value in (0, 1), which captures the relevant regime for compressed sensing. This improves upon the existing average-case hardness result of Wang et al., which is limited to $\delta = o(1)$. [ABSTRACT FROM AUTHOR]

In this paper, we bring forward a completely perturbed nuclear norm minimization method to tackle a formulation of completely perturbed low-rank matrices recovery. In view of the matrix version of the restricted isometry property (RIP) and the Frobeniusrobust rank null space property (FRNSP), this paper extends the investigation to a completely perturbed model taking into consideration not only noise but also perturbation, derives sufficient conditions guaranteeing that low-rank matrices can be robustly and stably reconstructed under the completely perturbed scenario, as well as finally presents an upper bound estimation of recovery error. The upper bound estimation can be described by two terms, one concerning the total noise, and another regarding the best r-approximation error. Specially, we not only improve the condition corresponding with RIP, but also ameliorate the upper bound estimation in case the results reduce to the general case. Furthermore, in the case of E = 0, the obtained conditions are optimal. [ABSTRACT FROM AUTHOR]

We consider the question of estimating a real low-complexity signal (such as a sparse vector or a low-rank matrix) from the phase of complex random measurements. We show that in this phase-only compressive sensing (PO-CS) scenario, we can perfectly recover such a signal with high probability and up to global unknown amplitude if the sensing matrix is a complex Gaussian random matrix and the number of measurements is large compared to the complexity level of the signal space. Our approach proceeds by recasting the (non-linear) PO-CS scheme as a linear compressive sensing model built from a signal normalization constraint, and a phase-consistency constraint imposing any signal estimate to match the observed phases in the measurement domain. Practically, stable and robust estimation of the signal direction is achieved from any instance optimal algorithm of the compressive sensing literature (such as basis pursuit denoising). This is ensured by proving that the matrix associated with this equivalent linear model satisfies with high probability the restricted isometry property under the above condition on the number of measurements. We finally observe experimentally that robust signal direction recovery is reached at about twice the number of measurements needed for signal recovery in compressive sensing. [ABSTRACT FROM AUTHOR]

This paper considers block sparse recovery and rank minimization problems from incomplete linear measurements. We study the weighted l p − l 1 (0 < p ≤ 1) norms as a nonconvex metric for recovering block sparse signals and low-rank matrices. Based on the block p -restricted isometry property (abbreviated as block p -RIP) and matrix p -RIP, we prove that the weighted l p − l 1 minimization can guarantee the exact recovery for block sparse signals and low-rank matrices. We also give the stable recovery results for approximately block sparse signals and approximately low-rank matrices in noisy measurements cases. Our results give the theoretical support for block sparse recovery and rank minimization problems. [ABSTRACT FROM AUTHOR]

Aiming at the problems that common chaotic mapping has low randomness, sequence elements has strong correlation, and constructing the measurement matrix elements requires interval sampling to satisfy the independence of data statistics, a new composite chaotic system is constructed by cascading quantum Logistic chaotic system and generalized Fibonacci sequence. In terms of information entropy, spatial characteristics and correlation coefficients, different chaotic measurement matrices are quantitatively analyzed to verify that the proposed chaotic system has ergodicity and high chaos. Moreover, the sequence elements have low correlation, which satisfies the independence of data statistics. At the same time, it is proved that the compressed sensing measurement matrix constructed by the proposed chaotic system satisfies the RIP condition. Simulation and discussion on one-dimensional sparse signal and two-dimensional image show that, compared with other measurement matrices, when the sampling rate is 1/2, the proposal increases the success rate of reconstructing one-dimensional sparse signals by 4 %, and increases the SNR rate of reconstructing two-dimensional images by 0. 2dB. It improves the data utilization rate and overcomes the great waste of data resources caused by the interval sampling of other chaotic measurement matrices. [ABSTRACT FROM AUTHOR]

The goal of Sparse Convex Optimization is to optimize a convex function f under a sparsity constraint s where s is the target number of non-zero entries in a feasible solution (sparsity) and 1 is an approximation factor. There has been a lot of work to analyze the sparsity guarantees of various algorithms (LASSO, Orthogonal Matching Pursuit (OMP), Iterative Hard Thresholding (IHT)) in terms of the Restricted Condition Number The best known algorithms guarantee to find an approximate solution of value f(x*) + ffl with the sparsity bound of = O where x* is the target solution. We present a new Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes significant progress on this problem by bringing the bound down to = O(k), which has been shown to be tight for a general class of algorithms including LASSO, OMP, and IHT. This is achieved without significant sacrifice in the runtime efficiency compared to the fastest known algorithms. We also provide a new analysis of OMP with Replacement (OMPR) for general f, under the condition s > s 4, which yields compressed sensing bounds under the Restricted Isometry Property (RIP). When compared to other compressed sensing approaches, it has the advantage of providing a strong tradeoff between the RIP condition and the solution sparsity, while working for any general function f that meets the RIP condition. [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]

Compressed sensing theory provides a new approach to acquire data as a sampling technique and makes sure that sparse signals 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 sparse compressed sensing matrices from constant dimension codes are constructed and the coherence of the matrices are computed. Furthermore, the maximum sparsity of recovering the sparse signals by using our matrices is obtained. Meanwhile, the numerical simulations are made among our matrices from constant dimension codes, R. DeVore's matrices, matrices from p -ary BCH codes and random matrices. Moreover, the deterministic sparse compressed sensing matrices can be constructed from certain Steiner structures. Finally, a general analysis indicates that the deterministic sparse compressed sensing matrices from constant dimension codes can recover signals of arbitrary sparsity order with any number of budged rows in some Euclid spaces with proper dimensions. [ABSTRACT FROM AUTHOR]

Dimensionality reduction is in demand to reduce the complexity of solving large-scale problems with data lying in latent low-dimensional structures in machine learning and computer vision. Motivated by such need, in this work we study the Restricted Isometry Property (RIP) of Gaussian random projections for low-dimensional subspaces in R N , and rigorously prove that the projection Frobenius norm distance between any two subspaces spanned by the projected data in R n (n < N) remain almost the same as the distance between the original subspaces with probability no less than 1 − e − O (n). Previously the well-known Johnson-Lindenstrauss (JL) Lemma and RIP for sparse vectors have been the foundation of sparse signal processing including Compressed Sensing. As an analogy to JL Lemma and RIP for sparse vectors, this work allows the use of random projections to reduce the ambient dimension with the theoretical guarantee that the distance between subspaces after compression is well preserved. [ABSTRACT FROM AUTHOR]

This paper presents an Analog-to-Information Conversion (AIC) model to acquire and simultaneously compress, with Time-Interleaved Analog-to-Digital Converters (TI-ADC), wide-band analog signals that can be sparse in a variety of domains. Compared with current AIC acquisition methods also based on TI-ADC, the proposed scheme represents a useful generalisation because it embodies a recently theoretically proved Restricted Isometry Property (RIP)-compliant sampling operator structure in the Compressed Sensing (CS) framework and, hence, favours the universal acquisition requirement for stable information recovery. The proposed model achieves its enhanced measurement characteristics by means of a Digital Signal Processing (DSP)-based encoding multi-coset core that operates completely in the low-rate section. [ABSTRACT FROM AUTHOR]

The restricted isometry property (RIP) and restricted conformal property (RCP) are two fundamental properties widely used in compressive sensing (CS) for sampling sparse signals. These two properties are sufficient to preserve the magnitude of a signal vector and the angle between two signal vectors in the compressively sensed band domain (CSBD), respectively. This article derives two new CS properties for hyperspectral signal vectors (HSVs), to be called the restricted entropy property (REP) and restricted spectrum property (RSP), which can be shown to preserve the entropy of an HSV and the spectral similarity between two HSVs in CSBD in correspondence to RIP and RCP, respectively. These two properties enable hyperspectral analysis algorithms to be directly applied to CSBD without loss of data integrity, while the dimensionality of CSBD can be considerably reduced. Most importantly, REP and RSP preserve exploitation algorithm performance without the need for decompression so as to avoid specifying a sparse basis. [ABSTRACT FROM AUTHOR]

In this paper, we consider the recovery of $k$ -sparse signals using the weighted $\ell _{p}$ ($0< p \leqslant 1$) minimization when some partial prior information on the support is available. First, we present a unified analysis of restricted isometry constant $\delta _{tk}$ with $d< t \leqslant 2d$ ($d \geqslant 1$ is determined by the prior support information) for sparse signal recovery by the weighted $\ell _{p}$ ($0< p \leqslant 1$) minimization in both noiseless and noisy settings. This result fills a vacancy on $\delta _{tk}$ with $t< 2$ , compared with previous works on $\delta _{(a+1)k}$ ($a>1$). Second, we provide a sufficient condition on $\delta _{tk}$ with $1< t \leqslant 2$ for the recovery of sparse signals using the $\ell _{p}$ ($0< p \leqslant 1$) minimization, which extends the existing optimal result on $\delta _{2k}$ in the literature. Last, various numerical examples are presented to demonstrate the better performance of the weighted $\ell _{p}$ ($0< p \leqslant 1$) minimization is achieved when the accuracy of prior information on the support is at least 50%, compared with that of the $\ell _{p}$ ($0< p \leqslant 1$) minimization. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS) is a new data acquisition theory taking full use of the sparsity of signals. It reveals that higher-dimensional sparse signals can be reconstructed from fewer nonadaptive linear measurements. The construction of CS matrices in CS is the key problem. In this paper, the deterministic CS matrices from optimal codebooks are constructed. Furthermore, the maximum sparsity of recovering the sparse signals by using our CS matrices are obtained. Meanwhile, a comparison is made with the CS matrices constructed by DeVore based on polynomials over finite fields. In the numerical simulations, our CS matrix outperforms DeVore ′ s matrix in the process of recovering sparse signals. [ABSTRACT FROM AUTHOR]

The restricted isometry property (RIP) is an integral tool in the analysis of various inverse problems with sparsity models. Motivated by the applications of compressed sensing and dimensionality reduction of low-rank tensors, we propose generalized notions of sparsity and provide a unified framework for the corresponding RIP, in particular when combined with isotropic group actions. Our results extend an approach by Rudelson and Vershynin to a much broader context including commutative and non-commutative function spaces. Moreover, our Banach space notion of sparsity applies to affine group actions. The generalized approach in particular applies to high-order tensor products. [ABSTRACT FROM AUTHOR]

Parallel acquisition systems are employed successfully in a variety of different sensing applications when a single sensor cannot provide enough measurements for a high-quality reconstruction. In this paper, we consider compressed sensing (CS) for parallel acquisition systems when the individual sensors use subgaussian random sampling. Our main results are a series of uniform recovery guarantees which relate the number of measurements required to the basis in which the solution is sparse and certain characteristics of the multi-sensor system, known as sensor profile matrices. In particular, we derive sufficient conditions for optimal recovery, in the sense that the number of measurements required per sensor decreases linearly with the total number of sensors, and demonstrate explicit examples of multi-sensor systems for which this holds. We establish these results by proving the so-called Asymmetric Restricted Isometry Property (ARIP) for the sensing system and use this to derive both nonuniversal and universal recovery guarantees. Compared to existing work, our results not only lead to better stability and robustness estimates but also provide simpler and sharper constants in the measurement conditions. Finally, we show how the problem of CS with block-diagonal sensing matrices can be viewed as a particular case of our multi-sensor framework. Specializing our results to this setting leads to a recovery guarantee that is at least as good as existing results. [ABSTRACT FROM AUTHOR]

In this paper, we study tail inequalities of the largest eigenvalue of a matrix infinitely divisible (i.d.) series, which is a finite sum of fixed matrices weighted by i.d. random variables. We obtain several types of tail inequalities, including Bennett-type and Bernstein-type inequalities. This allows us to further bound the expectation of the spectral norm of a matrix i.d. series. Moreover, by developing a new lower-bound function for $Q(s)=(s+1)\log (s+1)-s$ that appears in the Bennett-type inequality, we derive a tighter tail inequality of the largest eigenvalue of the matrix i.d. series than the Bernstein-type inequality when the matrix dimension is high. The resulting lower-bound function is of independent interest and can improve any Bennett-type concentration inequality that involves the function $Q(s)$. The class of i.d. probability distributions is large and includes Gaussian and Poisson distributions, among many others. Therefore, our results encompass the existing work on matrix Gaussian series as a special case. Lastly, we show that the tail inequalities of a matrix i.d. series have applications in several optimization problems including the chance constrained optimization problem and the quadratic optimization problem with orthogonality constraints. In addition, we also use the resulting tail bounds to show that random matrices constructed from i.d. random variables satisfy the restricted isometry property (RIP) when it acts as a measurement matrix in compressed sensing. [ABSTRACT FROM AUTHOR]

In this paper, we use the block orthogonal matching pursuit (BOMP) algorithm to recover block sparse signals x from measurements y = A x + v , where v is an ℓ 2 -bounded noise vector (i.e., ‖ v ‖ 2 ≤ ϵ for some constant ϵ). We investigate some sufficient conditions based on the block restricted isometry property (block-RIP) for exact (when v = 0) and stable (when v ≠ 0) recovery of block sparse signals x . First, on the one hand, we show that if A satisfies the block-RIP with δ K + 1 < 1 / K + 1 , then every block K -sparse signal x can be exactly or stably recovered by BOMP in K iterations. On the other hand, we show that, for any K ≥ 1 and 1 / K + 1 ≤ δ < 1 , there exists a matrix A satisfying the block-RIP with δ K + 1 = δ and a block K -sparse signal x such that BOMP may fail to recover x in K iterations. Then, we study some sufficient conditions for recovering block α -strongly-decaying K -sparse signals. We show that if A satisfies the block-RIP with δ K + 1 < 2 / 2 , then every α -strongly-decaying block K -sparse signal can be exactly or stably recovered by BOMP in K iterations under some conditions on α. Our newly found sufficient condition on the block-RIP of A is less restrictive than that for ℓ 1 minimization for this special class of sparse signals. Furthermore, for any K ≥ 1 , α > 1 and 2 / 2 ≤ δ < 1 , the recovery of x may fail in K iterations for a sensing matrix A which satisfies the block-RIP with δ K + 1 = δ. Finally, we study some sufficient conditions for partial recovery of block sparse signals. Specifically, if A satisfies the block-RIP with δ K + 1 < 2 / 2 , then BOMP is guaranteed to recover some blocks of x if these blocks satisfy a sufficient condition. We further show that this condition is also sharp. [ABSTRACT FROM AUTHOR]

In this paper, we present a unified analysis of RIP bounds for sparse signals recovery by using ℓ p minimization with 0 < p ≤ 1 and provide optimal RIP bounds which can guarantee sparse signals recovery via ℓ p minimization for each p ∈ (0 , 1 ] in both noiseless and noisy settings. It is shown that if the measurement matrix Φ satisfies the RIP condition δ 2 k < δ (p) , where δ (p) will be specified in the context, then all k -sparse signals x can be recovered stably via the constrained ℓ p minimization based on b = Φ x + z , where z is one type of noise. Furthermore, we show that for any ϵ > 0 , δ 2 k < δ (p) + ϵ is not sufficient to guarantee the exact recovery of all k -sparse signals. We also apply the results to the cases of low rank matrix recovery and the reconstruction of sparse vectors in terms of redundant dictionary. In particular, when p = 1 , the corresponding constant δ (1) = 2 2 , this sharp bound was shown by T. Cai and A. Zhang in their work. Thus, we give a complete characterization for optimal RIP bounds δ 2 k via ℓ p minimization for k -sparse signals recovery with 0 < p ≤ 1. Our approaches are based on some ideas of sparse representation of a given polytope, which was firstly used by T. Cai and A. Zhang. [ABSTRACT FROM AUTHOR]

Current research mainly focuses on the case that a single sensor node sends data, and the transmission efficiency is low. Using multiple sensor nodes to send data at the same time can improve the transmission efficiency, but there is interference between user' s data. Compressed sensing (CS) theory is applied to underwater acoustic sensor networks. A large-capacity cooperative communication method was proposed to realize simultaneous transmission of data by multiple nodes. Using the sparse characteristics of sensor nodes, simultaneous transmission of data from multiple source nodes is equivalent to the measurement process in CS. It is proved that the transmission characteristics of multiple nodes can satisfy the restricted isometry property ( RIP) in the CS theory. The destination node can recover the data of multiple concurrent sensor nodes by the reconstruction algorithm. [ABSTRACT FROM AUTHOR]

Although hyperspectral technology has continued to improve over the years, it is still limited to size, weight, and power (SWaP) constraints. One major issue is the need to sample a large number of very fine spectral bands. Such prohibitively large size of hyperpsectral data creates challenges in both data archival and processing. Compressive sensing (CS) is an enabling technology for reducing the overall data processing and SWaP requirements. This paper explores the viability of performing classification for hyperspectral data on a compressively sensed band domain (CSBD) via CS instead of the original data space, without performing sparse reconstruction. In particular, the well-known restricted isometry property (RIP) and a random spectral sampling strategy are explored for hyperspectral image classification (HSIC) in CSBD. A mathematical analysis is also presented to show that the classification error can be expressed in terms of the restricted isometry constant (RIC) so that the HSIC in the original full-band data space can be achieved in CSBD provided that sufficient band-sensing conditions are met. To validate the proposed CS-HSIC a set of real hyperspectral image experiments are performed where a commonly used spectral–spatial classification algorithm based on support vector machine (SVM) and edge-preserving filters (EPFs) is implemented for a comparative study and analysis. The results clearly demonstrate the potential of CS-HSIC in future research directions. [ABSTRACT FROM AUTHOR]

• Leveraging subspace information can enhance the reconstruction accuracy of low-rank matrix. • The designed affine map outperforms the randomly generated affine map in terms of reconstruction accuracy. • Adapting the representation of low-rank matrices to the noise level can achieve minimum mean square error. • The proposed two-step low-rank matrix reconstruction algorithm achieves a robust performance with low complexity. The problem of low-rank matrix reconstruction arises in various applications in communications and signal processing. The state of the art research largely focuses on the recovery techniques that utilize affine maps satisfying the restricted isometry property (RIP). However, the affine map design and reconstruction under a priori information, i.e., column or row subspace information, has not been thoroughly investigated. To this end, we present designs of affine maps and reconstruction algorithms that fully exploit the low-rank matrix subspace information. Compared to the randomly generated affine map, the proposed affine map design permits an enhanced reconstruction. In addition, we derive an optimal representation of low-rank matrices, which is exploited to optimize the rank and subspace of the estimate by adapting them to the noise level in order to achieve the minimum mean square error (MSE). Moreover, in the case when the subspace information is not a priori available, we propose a two-step algorithm, where, in the first step, it estimates the column subspace of a low-rank matrix, and in the second step, it exploits the estimated information to complete the reconstruction. The simulation results show that the proposed algorithm achieves robust performance with much lower complexity than existing reconstruction algorithms. [ABSTRACT FROM AUTHOR]

The study of the restricted isometry property (RIP) of corrupted random matrices is particularly important in the field of compressed sensing (CS) with corruptions. If a matrix still satisfies the RIP after that a certain portion of rows are erased, then we say that this matrix has the strong restricted isometry property (SRIP). In the field of compressed sensing, random matrices which satisfy certain moment conditions are of particular interest. Among these matrices, those with entries generated from i.i.d. Gaussian or symmetric Bernoulli random variables are often typically considered. Recent studies have shown that matrices with entries generated from i.i.d. Gaussian random variables satisfy the SRIP under arbitrary erasure of rows with high probability. In this paper, we study the erasure robustness property of Bernoulli random matrices. Our main result shows that with overwhelming probability, the SRIP holds for Bernoulli random matrices. Moreover, our analysis leads to a robust version of the famous Johnson–Lindenstrauss lemma for Bernoulli random matrices. [ABSTRACT FROM AUTHOR]

• A new computationally tractable estimator for solving Poisson compressed sensing problems using the square-root of the Jensen Shannon Divergence. • Analysis of interesting statistical properties of the SQJSD with relevance to Poisson compressed sensing: triangle inequality, and properties of mean and variance of SQJSD 'V particular independence of underlying signal and number of measurements. • Analytical error bounds for Poisson compressed sensing using the new estimator, for underlying signals that are sparse or compressible in any orthonormal basis. • Advantages of SQJSD over the Poisson negative log-likelihood by means of a more principled method of parameter selection. • Extensive numerical results for Poisson compressed sensing. Recovery error bounds in compressed sensing under Gaussian or uniform bounded noise do not translate easily to the case of Poisson noise. Reasons for this include the signal dependent nature of Poisson noise, and also the fact that the negative log likelihood in case of a Poisson distribution (which is directly related to the generalized Kullback–Leibler divergence) is not a metric and does not obey the triangle inequality. There exist prior theoretical results in the form of provable error bounds for computationally tractable estimators for compressed sensing problems under Poisson noise. However, these results do not apply to realistic compressive systems, which must obey some crucial constraints such as non-negativity and flux preservation. On the other hand, there exist provable error bounds for such realistic systems in the published literature, but they are for estimators that are computationally intractable. In this paper, we develop error bounds for a computationally tractable estimator which also applies to realistic compressive systems obeying the required constraints. The focus of our technique is on the replacement of the generalized Kullback–Leibler divergence, with an information theoretic metric - namely the square root of the Jensen–Shannon divergence, which is related to an approximate, symmetrized version of the Poisson log likelihood function. We show that our method allows for very simple proofs of the error bounds. We also propose and prove several interesting statistical properties of the square root of Jensen–Shannon divergence, a well-known information-theoretic metric, and exploit other known ones. Numerical experiments are performed showing the practical use of the technique in signal and image reconstruction from compressed measurements under Poisson noise. Our technique has the following features: (i) It is applicable to signals that are sparse or compressible in any orthonormal basis. (ii) It works with high probability for any randomly generated sensing matrix that obeys the non-negativity and flux preservation constraints, and is derived from a 'base matrix' that obeys the restricted isometry property. (iii) Most importantly, our proposed estimator uses parameters that are purely statistically motivated and signal independent, as opposed to techniques (such as those based on the Poisson negative log-likelihood or ℓ 2 data-fidelity) that require the choice of a regularization or signal sparsity parameter which are unknown in practice. [ABSTRACT FROM AUTHOR]

Face recognition under natural scenes is a significant challenge in pattern recognition research. With the success of sparse representation-based classification in related fields, face recognition based on compressed sensing (CS) theory has received increasing attention. These CS-based approaches produce excellent results when dealing with face data from experimental environments, but are inadequate when dealing with images from natural scenes. For solving this problem, a novel Generalized Compressed Sensing (GCS) framework is proposed in this paper. The main innovations of this paper are three-fold. First, with reference to the commutative property of the inner product, GCS recovery treats the original CS matrix, not the original signal, as the processing object. Second, in order to ensure the reliability and feasibility of GCS recovery, a QR-based vision matrix learning method is presented to realize face information embedding for the original CS matrix. Third, to balance the restricted isometry property (RIP) of the original CS matrix for CS sampling and its sparsity for GCS recovery, a low density parity check code is introduced to generate the original CS matrix. With this full CS framework including CS sampling and GCS recovery, the final generalized l 1 -norm optimal solution can be used as the criterion for face recognition. Experimental results show that, compared with conventional approaches to CS recognition, the proposed method achieves a significant performance for face recognition tasks under natural scenes. [ABSTRACT FROM AUTHOR]

The hard thresholding technique plays a vital role in the development of algorithms for sparse signal recovery. By merging this technique and heavy-ball acceleration method which is a multi-step extension of the traditional gradient descent method, we propose the so-called heavy-ball-based hard thresholding (HBHT) and heavy-ball-based hard thresholding pursuit (HBHTP) algorithms for signal recovery. It turns out that the HBHT and HBHTP can successfully recover a k -sparse signal if the restricted isometry constant of the measurement matrix satisfies δ 3 k < 0. 618 and δ 3 k < 0. 577 , respectively. The guaranteed success of HBHT and HBHTP is also shown under the conditions δ 2 k < 0. 356 and δ 2 k < 0. 377 , respectively. Moreover, the finite convergence of HBHTP and stability of the two algorithms are also established in this paper. Simulations on random problem instances are performed to compare the performance of the proposed algorithms and several existing ones. Empirical results indicate that the HBHTP performs very comparably to a few existing algorithms and it takes less average time to achieve the signal recovery than these existing methods. [ABSTRACT FROM AUTHOR]

The problem of how to find a sparse representation of a signal is an important one in applied and computational harmonic analysis. It is closely related to the problem of how to reconstruct a sparse vector from its projection in a much lower-dimensional vector space. This is the setting of compressed sensing, where the projection is given by a matrix with many more columns than rows. We introduce a class of random matrices that can be used to reconstruct sparse vectors in this paradigm. These matrices satisfy the restricted isometry property with overwhelming probability. We also discuss an application in dimensionality reduction where we initially discovered this class of matrices. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering a group sparse vector from a small number of linear measurements. In the past, the common approach has been to use various “group sparsity-inducing” norms such as the Group LASSO norm for this purpose. By using the theory of convex relaxations, we show that it is also possible to use $\ell _1$ -norm minimization for group sparse recovery. We introduce a new concept called group robust null space property (GRNSP), and show that, under suitable conditions, a group version of the restricted isometry property (GRIP) implies the GRNSP, and thus leads to group sparse recovery. When all groups are of equal size, our bounds are sometimes less conservative than known bounds. Moreover, our results apply even to situations where the groups have different sizes. When specialized to conventional sparsity, our bounds reduce to one of the well-known “best possible” conditions for sparse recovery. This relationship between GRNSP and GRIP is new even for conventional sparsity, and substantially streamlines the proofs of some known results. Using this relationship, we derive bounds on the $\ell _p$ -norm of the residual error vector for all $p \in [1,2]$ , and not just when $p = 2$. When the measurement matrix consists of random samples of a sub-Gaussian random variable, we present bounds on the number of measurements, which are sometimes less conservative than currently known bounds. [ABSTRACT FROM AUTHOR]

Highlights • We propose a novel penalty function for CS using integral convolution approximation. • Our criterion dose not underestimate the large component in signal recovery. • Our methods perform well under both the Gaussian random sensing matrix satisfying RIP and the highly coherent sensing matrix. • We carry out a series of experiments to verify our analysis. Abstract In this paper, we propose a novel nonconvex penalty function for compressed sensing using integral convolution approximation. It is well known that an unconstrained optimization criterion based on ℓ 1 -norm easily underestimates the large component in signal recovery. Moreover, most methods either perform well only under the Gaussian random measurement matrix satisfying restricted isometry property or the highly coherent measurement matrix, which both can not be established at the same time. We introduce a new solver to address both of these concerns by adopting a frame of the difference between two convex functions with integral convolution approximation. What's more, to better boost the recovery performance, a weighted version of it is also provided. Experimental results suggest the effectiveness and robustness of our methods through several signal reconstruction examples in term of success rate and signal-to-noise ratio. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of observability of a linear dynamical system from compressive measurements and the knowledge of its external inputs. Observability of a high-dimensional system state in general requires a correspondingly large number of measurements. We show that if the initial state vector admits a sparse representation, the number of measurements can be significantly reduced by using random projections for obtaining the measurements. Our analysis gives sufficient conditions for the restricted isometry property of the observability matrix to hold, which leads to guarantees for the observability of the system. Our results depend only on the properties of system transfer and observation matrices, and are derived using tools from probability theory and compressed sensing. Unlike the prior work in this direction, our results are applicable to systems with an arbitrary nonzero system transfer matrix. Moreover, our results are stronger than the existing results in the regime where they are comparable. [ABSTRACT FROM AUTHOR]

Abstract Compressive ghost imaging (CGI) is a single-pixel imaging technique and has attracted the attention of many researchers in the field. Traditional techniques for CGI are very sensitive to environmental noises. In this paper, we study environmental noises in CGI (including time-varying noise and constant background noise). We propose a modified compressive ghost imaging which combines the normalization and blocking of the DC term of the signal to improve the image quality. Time-varying noises are removed by normalization whereas constant background noise is eliminated by the DC blocking. DC blocking is done by subtracting each data and measurement matrix from the average data and the average of all the measurement matrices, respectively. Also, this subtraction optimizes 0–1 binary patterns for CGI algorithm to satisfy restricted isometry property (RIP). Thus, this denoising method offers a very effective way to promote the implementation of single-pixel imaging in real applications such as imaging low-contrast objects even in the presence of environmental illumination. This method is verified both experimentally and by simulation. The calculated signal to noise ratio is improved significantly in the simulation and experiment. [ABSTRACT FROM AUTHOR]