Search

The compressive sensing (CS) framework offers a cost-effective alternative to dense alias-free sampling. Designing seismic layouts based on the CS technique imposes the use of specific sampling patterns in addition to the logistical and geophysical requirements. We propose a two-step design process for generating CS-based schemes suitable for seismic applications. During the first step, uniform random sampling is used to generate a random scheme, which is supported theoretically by the restricted isometry property. Following that, designated samples are added to the random scheme to control the maximum distance between adjacent sources (or receivers). The null space property theoretically justifies the additional samples of the second step. Our sampling method generates sampling patterns with a CS theoretical background, controlled distance between adjacent samples, and a flexible number of active and omitted samples. The robustness of two-step sampling schemes for reallocated samples is investigated and CS reconstruction tests are performed. In addition, using this approach, a CS-based 3D seismic survey is designed, and the distributions of traces in fold maps and rose diagrams are analyzed. It is shown that the two-step scheme is suitable for CS-based seismic surveys and field applications. [ABSTRACT FROM AUTHOR]

Let M be a smooth submanifold of R n equipped with the Euclidean (chordal) metric. This note considers the smallest dimension m for which there exists a bi-Lipschitz function f : M ↦ R m with bi-Lipschitz constants close to one. The main result bounds the best achievable embedding dimension m below in terms of the Lipschitz constants of f as well as the reach, volume, diameter, and dimension of M. This new lower bound is then applied to show that prior upper bounds for m via random matrices by Eftekhari and Wakin [6] are near-optimal in a wide range of settings. This supports random linear maps as being nearly as efficient as nonlinear maps at reducing the ambient dimension for manifold data in many situations. Along the way, we also prove results concerning the impossibility of achieving better nonlinear measurement maps with the Restricted Isometry Property (RIP) in compressive sensing applications. [ABSTRACT FROM AUTHOR]

We know that compressive sensing can establish stable sparse recovery results from highly undersampled data under a restricted isometry property condition. In reality, however, numerous problems are coherent, and vast majority conventional methods might work not so well. Recently, it was shown that using the difference between ℓ 1 - and ℓ 2 -norm as a regularization always has superior performance. In this paper, we consider an adaptive ℓ p - ℓ 1 − 2 model where the ℓ p -norm with p ≥ 1 measures the data fidelity and the ℓ 1 − 2 -term measures the sparsity. This proposed model has the ability to deal with different types of noises and extract the sparse property even under high coherent condition. We use a proximal majorization-minimization technique to handle the non-convex regularization term and then employ a semismooth Newton method to solve the corresponding convex relaxation subproblem. We prove that the sequence generated by the semismooth Newton method admits fast local convergence rate to the subproblem under some technical assumptions. Finally, we do some numerical experiments to demonstrate the superiority of the proposed model and the progressiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We present a detailed analysis of the unconstrained ℓ 1 -weighted LASSO method for recovery of sparse data from its observation by randomly generated matrices, satisfying the restricted isometry property (RIP) with constant δ < 1 , and subject to negligible measurement and compressibility errors. We prove that if the data are k-sparse, then the size of support of the LASSO minimizer, s, maintains a comparable sparsity, s ⩽ C δ k . For example, if δ = 0.7 then s < 11 k and a slightly smaller δ = 0.4 yields s < 4 k . We also derive new ℓ 2 / ℓ 1 error bounds which highlight precise dependence on k and on the LASSO parameter λ , before the error is driven below the scale of negligible measurement/ and compressiblity errors. [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]

This note extends an attribute of the LASSO procedure to a whole class of related procedures, including square-root LASSO, square LASSO, LAD-LASSO, and an instance of generalized LASSO. Namely, under the assumption that the input matrix satisfies an ℓ p -restricted isometry property (which in some sense is weaker than the standard ℓ 2 -restricted isometry property assumption), it is shown that if the input vector comes from the exact measurement of a sparse vector, then the minimizer of any such LASSO-type procedure has sparsity comparable to the sparsity of the measured vector. The result remains valid in the presence of moderate measurement error when the regularization parameter is not too small. [ABSTRACT FROM AUTHOR]

In this work, we provide non-asymptotic, probabilistic guarantees for successful recovery of the common nonzero support of jointly sparse Gaussian sources in the multiple measurement vector (MMV) problem. The support recovery problem is formulated as the marginalized maximum likelihood (or type-II ML) estimation of the variance hyperparameters of a joint sparsity inducing Gaussian prior on the source signals. We derive conditions under which the resulting nonconvex constrained optimization perfectly recovers the nonzero support of a joint-sparse Gaussian source ensemble with arbitrarily high probability. The support error probability decays exponentially with the number of MMVs at a rate that depends on the smallest restricted singular value and the nonnegative null space property of the self Khatri-Rao product of the sensing matrix. Our analysis confirms that nonzero supports of size as high as $O(m^{2})$ are recoverable from $m$ measurements per sparse vector. Our derived sufficient conditions for support consistency of the proposed constrained type-II ML solution also guarantee the support consistency of any global solution of the multiple sparse Bayesian learning (M-SBL) optimization whose nonzero coefficients lie inside a bounded interval. For the case of noiseless measurements, we further show that a single MMV is sufficient for perfect recovery of the $k$ -sparse support by M-SBL, provided all subsets of $k + 1$ columns of the sensing matrix are linearly independent. [ABSTRACT FROM AUTHOR]

We present a compressive radar design that combines multitone linear frequency modulated (LFM) waveforms in the transmitter with a classical stretch processor and sub-Nyquist sampling in the receiver. The proposed compressive illumination scheme has fewer random elements resulting in reduced storage and complexity for implementation and calibration than previously proposed compressive radar designs based on stochastic waveforms. We analyze this illumination scheme for the task of a joint range-angle of arrival estimation in the multi-input and multi-output (MIMO) radar system. We present recovery guarantees for the proposed illumination technique. We show that for a sufficiently large number of modulating tones, the system achieves high-resolution in range and successfully recovers the range and angle-of-arrival of targets in a sparse scene. Furthermore, we demonstrate the stability of recovery of targets in range and angle of arrival domain in the continuum. Finally, we present simulation results to illustrate the recovery performance as a function of system parameters. [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]

Phase noise (PN) introduced by the oscillator at the base station and user side severely degrades the channel estimation performance. This paper investigates the impact of PN on downlink compressive channel estimation in massive multiple-input multiple-output (MIMO) systems. Particularly, the downlink compressive channel estimation with PN is modeled as a sparse signal recovery problem with additive correlated perturbation on the pilot matrix, which is a general formulation for both non-synchronous and synchronous PN. Based on this signal model, the performance of the equivalent sensing matrix is analyzed by invoking restricted isometry property (RIP) in compressive sensing. In addition, the upper bound for $l_{1}$ -minimization based channel estimation method and tight channel estimation bound are derived in the framework of RIP and Oracle least square methodology, respectively. Finally, we propose a PN-aware sparse Bayesian learning (PNA-SBL) algorithm to improve the channel estimation performance in the presence of synchronous PN. Simulation results demonstrate our analysis and superiority of the proposed PNA-SBL algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a new image sensor architecture for fast and accurate compressive sensing (CS) of natural images. Measurement matrices usually employed in CS CMOS image sensors are recursive pseudo-random binary matrices. We have proved that the restricted isometry property of these matrices is limited by a low sparsity constant. The quality of these matrices is also affected by the non-idealities of pseudo-random number generators (PRNG). To overcome these limitations, we propose a hardware-friendly pseudo-random ternary measurement matrix generated on-chip by means of class III elementary cellular automata (ECA). These ECA present a chaotic behavior that emulates random CS measurement matrices better than other PRNG. We have combined this new architecture with a block-based CS smoothed-projected Landweber reconstruction algorithm. By means of single value decomposition, we have adapted this algorithm to perform fast and precise reconstruction while operating with binary and ternary matrices. Simulations are provided to qualify the approach. [ABSTRACT FROM AUTHOR]

We investigate the problem of recovering jointly r -rank and s -bisparse matrices from as few linear measurements as possible, considering arbitrary measurements as well as rank-one measurements. In both cases, we show that m ≍ r s ln (e n / s) measurements make the recovery possible in theory, meaning via a nonpractical algorithm. In case of arbitrary measurements, we investigate the possibility of achieving practical recovery via an iterative-hard-thresholding algorithm when m ≍ r s γ ln (e n / s) for some exponent γ > 0. We show that this is feasible for γ = 2 , and that the proposed analysis cannot cover the case γ ≤ 1. The precise value of the optimal exponent γ ∈ [ 1 , 2 ] is the object of a question, raised but unresolved in this paper, about head projections for the jointly low-rank and bisparse structure. Some related questions are partially answered in passing. For rank-one measurements, we suggest on arcane grounds an iterative-hard-thresholding algorithm modified to exploit the nonstandard restricted isometry property obeyed by this type of measurements. [ABSTRACT FROM AUTHOR]

Highlights • A joint Bayesian and optimization framework is proposed for sparse signal recovery. • Variational Bayesian (VB) is employed to perform the inference and Euclidean projection (EP) is utilized to impose sparsity. • A maximum likelihood estimator (MLE) of the Bayesian model to speed up the inference with a pre-determined step size is developed. • The convergence of this MLE-EP algorithm is analyzed and compared with the iterative shrinkage/thresholding algorithm. Abstract We develop an efficient algorithm, which can adaptively infer the step-size in each iteration, to recover sparse signal from compressive measurements. This algorithm is formulated as an iteratively alternating projection strategy; the first step projects the measurements/residuals to the signal space, implemented via a Bayesian model, and the second step projects the results obtained in the first step to the ℓ 1 -ball. Variational Bayesian (VB) is employed to perform the inference of the Bayesian model and Euclidean projection (EP) is utilized to impose sparsity; thus our algorithm is dubbed VB-EP. We further derive a maximum likelihood estimator (MLE) of the Bayesian model to speed up the inference with a pre-determined step size. The convergence of this MLE-EP algorithm is analyzed and compared with the iterative shrinkage/thresholding algorithm based on the restricted isometry property of the compressive sensing matrix. Simulation results verify the superior performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a new algorithm for compressive sensing that makes use of binary measurement matrices and achieves exact recovery of ultrasparse vectors in a single pass and without any iterations. Due to its noniterative nature, our algorithm is hundreds of times faster than $\ell _1$ -norm minimization and methods based on expander graphs, both of which require multiple iterations. Our algorithm can accommodate nearly sparse vectors, in which case, it recovers an index set of the largest components, and can also accommodate burst noise measurements. Compared to compressive sensing methods that are guaranteed to achieve exact recovery of all sparse vectors, our method requires fewer measurements. However, methods that achieve statistical recovery, that is, recovery of almost all but not all sparse vectors, can require fewer measurements than our method. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering sparse vectors from underdetermined linear measurements via $\ell _{p}$ -constrained basis pursuit. Previous analyses of this problem based on generalized restricted isometry properties have suggested that two phenomena occur if $p\neq 2$. First, one may need substantially more than $s \log (en/s)$ measurements (optimal for $p=2$ ) for uniform recovery of all $s$ -sparse vectors. Second, the matrix that achieves recovery with the optimal number of measurements may not be Gaussian (as for $p=2$ ). We present a new, direct analysis, which shows that in fact neither of these phenomena occur. Via a suitable version of the null space property, we show that a standard Gaussian matrix provides $\ell _{q}/\ell _{1}$ -recovery guarantees for $\ell _{p}$ -constrained basis pursuit in the optimal measurement regime. Our result extends to several heavier-tailed measurement matrices. As an application, we show that one can obtain a consistent reconstruction from uniform scalar quantized measurements in the optimal measurement regime. [ABSTRACT FROM AUTHOR]

Compressive sensing involves 3 main processes: signal sparse representation, linear encoding or measurement collection, and nonlinear decoding or sparse recovery. In the measurement process, a measurement matrix is used to sample only the components that best represent the signal. The choice of the measurement matrix has an important impact on the accuracy and the processing time of the sparse recovery process. Hence, the design of accurate measurement matrices is of vital importance in compressive sensing. Over the last decade, a number of measurement matrices have been proposed. Therefore, a detailed review of these measurement matrices and a comparison of their performances are strongly needed. This paper explains the foundation of compressive sensing and highlights the process of measurement by reviewing the existing measurement matrices. It provides a 3-level classification and compares the performance of 8 measurement matrices belonging to 4 different types using 5 evaluation metrics: the recovery error, processing time, recovery time, covariance, and phase transition diagram. The theoretical performance comparison is validated with experimental results, and the results show that the Circulant, Toeplitz, and Hadamard matrices outperform the other measurement matrices. [ABSTRACT FROM AUTHOR]

The columnwise Khatri-Rao product of two matrices is an important matrix type, reprising its role as a structured sensing matrix in many fundamental linear inverse problems. Robust signal recovery in such inverse problems is often contingent on proving the restricted isometry property (RIP) of a certain system matrix expressible as a Khatri-Rao product of two matrices. In this paper, we analyze the RIP of a generic columnwise Khatri-Rao product matrix by deriving two upper bounds for its kth order restricted isometry constant (k-RIC) for different values of k. The first RIC bound is computed in terms of the individual RICs of the real-valued input matrices participating in the Khatri-Rao product. The second RIC bound is probabilistic and is specified in terms of the input matrix dimensions. We show that the Khatri-Rao product of a pair of m x n sized random matrices comprising independent and identically distributed sub-Gaussian entries satisfies k-RIP with arbitrarily high probability, provided m exceeds O(√k log3/2 n). This is a substantially milder condition compared to O(k log n) rows needed to guarantee k-RIP of the input sub-Gaussian random matrices participating in the Khatri-Rao product. Our RIC bounds confirm that the Khatri-Rao product exhibits stronger restricted isometry compared to its constituent matrices for the same RIP order. The proposed RIC bounds are potentially useful in obtaining improved performance guarantees in several sparse signal recovery and tensor decomposition problems. [ABSTRACT FROM AUTHOR]

Recently, many works have focused on the characterization of non-linear dimensionality reduction methods obtained by quantizing linear embeddings, e.g., to reach fast processing time, efficient data compression procedures, novel geometry-preserving embeddings or to estimate the information/bits stored in this reduced data representation. In this work, we prove that many linear maps known to respect the restricted isometry property (RIP) can induce a quantized random embedding with controllable multiplicative and additive distortions with respect to the pairwise distances of the data points beings considered. In other words, linear matrices having fast matrix-vector multiplication algorithms (e.g., based on partial Fourier ensembles or on the adjacency matrix of unbalanced expanders) can be readily used in the definition of fast quantized embeddings with small distortions. This implication is made possible by applying right after the linear map an additive and random "dither" that stabilizes the impact of the uniform scalar quantization operator applied afterwards. For different categories of RIP matrices, i.e., for different linear embeddings of a metric space (K⊂Rn,ℓq) in (Rm,ℓp) with p,q≥1, we derive upper bounds on the additive distortion induced by quantization, showing that it decays either when the embedding dimension m increases or when the distance of a pair of embedded vectors in K decreases. Finally, we develop a novel "bi-dithered" quantization scheme, which allows for a reduced distortion that decreases when the embedding dimension grows and independently of the considered pair of vectors. [ABSTRACT FROM AUTHOR]

In compressive sensing, one important parameter that characterizes the various greedy recovery algorithms is the iteration bound which provides the maximum number of iterations by which the algorithm is guaranteed to converge. In this letter, we present a new iteration bound for the compressive sampling matching pursuit (CoSaMP) algorithm by certain mathematical manipulations including formulation of appropriate sufficient conditions that ensure passage of a chosen support through the two selection stages of CoSaMP, “Augment” and “Update”. Subsequently, we extend the treatment to the subspace pursuit (SP) algorithm. The proposed iteration bounds for both CoSaMP and SP algorithms are seen to be improvements over their existing counterparts, revealing that both CoSaMP and SP algorithms converge in fewer iterations than suggested by results available in literature. [ABSTRACT FROM AUTHOR]

• The restricted isometry property (RIP) and high-order RIP analysis results for the weighted ℓ r − ℓ 1 minimization method are presented. • Through a novel decomposition of the objective function into a difference of two convex functions, the weighted ℓ r − ℓ 1 minimization problem is solved via the difference of convex functions algorithms (DCA) directly. • Numerical experiments show that the DCA based weighted ℓ r − ℓ 1 minimization method gives satisfactory results in sparse recovery no matter whether the measurement matrix is coherent or not. • For highly coherent measurements, the proposed method even outperforms the state-of-art ℓ 1 − ℓ 2 minimization method. The weighted ℓ r − ℓ 1 minimization method with 0 < r ≤ 1 largely generalizes the classical ℓ r minimization method and achieves very good performance in compressive sensing. However, its restricted isometry property (RIP) and high-order RIP analysis results remain unknown. In this paper, we fill in this gap by adopting newly developed analysis tools. Moreover, through a novel decomposition of the objective function into a difference of two convex functions, we propose to solve the weighted ℓ r − ℓ 1 minimization problem via the difference of convex functions algorithms (DCA) directly. Numerical experiments show that our DCA based weighted ℓ r − ℓ 1 minimization method gives satisfactory results in sparse recovery no matter whether the measurement matrix is coherent or not. For highly coherent measurements, our proposed method even outperforms the state-of-art ℓ 1 − ℓ 2 minimization method. [ABSTRACT FROM AUTHOR]

Inspired by the compressive sensing (CS) theory, a new classifier based on compressed dictionary and Least Squares Support Vector Machine (LS-SVM) is proposed to deal with large scale problems. The coefficients of support vectors can be recovered from a few measurements if LS-SVM is approximated to sparse structure. Using the known Cholesky decomposition, we approximate the given kernel matrix to represent the coefficients of support vectors sparsely by a low-rank matrix that we have used as a dictionary. The proposed measurement matrix being coupled with the dictionary forms a compressed dictionary that proves to satisfy the restricted isometry property (RIP). Our classifier has the quality of low storage and computational complexity, high degree of sparsity and information preservation. Experiments on benchmark data sets show that our classifier has positive performance. [ABSTRACT FROM AUTHOR]

The restricted isometry property (RIP) is a fundamental property of a matrix, which enables sparse recovery. Informally, an m \times n matrix satisfies RIP of order k for the \ell p norm, if \Ax\p \approx \x\p for every vector x with at most k non-zero coordinates. For every 1 \leq p < \infty , we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this paper, only the cases p = 1 , 1 + 1 / \log n , and 2 were studied. Interestingly, our results show that the case p = 2 for all p\in [1,\infty )\setminus \2\ , as opposed to \widetilde \Theta (k) for $p=2$ . We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss the implications of our results for the stable sparse recovery problem as defined by Candès et al. [ABSTRACT FROM AUTHOR]

• Design of structured (example: constant modulus entries) compressive sensing matrices. • Enforcing a restricted isometry property formulated as distribution matching problem. • Distribution matching measured via maximum mean discrepancy and solved via learning. • Optimized matrix can outperform random matrices in numerical experiments. We introduce a learning-based algorithm to obtain a measurement matrix for compressive sensing related recovery problems. The focus lies on matrices with a constant modulus constraint which, e.g., represent a network of analog phase shifters in hybrid precoding/combining architectures. We interpret a matrix with restricted isometry property as a mapping from a high- to a low-dimensional hypersphere. We argue that points on the low-dimensional hypersphere should be uniformly distributed to combat measurement noise. This notion is formalized as an optimization problem which uses a maximum mean discrepancy metric as objective function. Recent success of such metrics in neural network related topics motivate a solution of the optimization problem based on machine learning. Numerical experiments show a better performance than random matrices that are typical for compressive sensing. Further, we adapt a method from the literature to the constant modulus constraint. This method can also compete with random matrices and harmonizes well with the proposed algorithm if it is used as an initialization. Lastly, we describe how other structural matrix constraints, e.g., a Toeplitz constraint, can be taken into account as well. [ABSTRACT FROM AUTHOR]

This paper proposes a new compressive sensing-based downlink channel state information (CSI) estimation scheme for frequency division duplexing (FDD) massive multiple-input multiple-output (MIMO) systems. The proposed scheme, which involves two-stage weighted block \ell _1-minimization, exploits the block sparse nature of the angular domain representation of the MIMO channel matrices and the existence of common scattering paths in the realistic propagation environment. In the first stage of the implemented scheme, a conventional block \ell _1-minimization program is solved to extract the information about the common/individual supports of the multiuser channel matrices. In the second stage, a weighted block \ell _1-minimization algorithm, the weighting coefficients of which are suitably chosen to exploit the acquired support information, is used to estimate the channel matrices. The analytic performance guarantees of the proposed scheme are specified based on the block restricted isometry property of the sensing matrix. Specifically, the upper bounds of the \ell _2-norm reconstruction error are derived using various assumptions regarding the weighting. The obtained analytical results enable a discussion of the selection of weighting coefficients to enhance the CSI estimation performance, and the determination of a sufficient condition under which the proposed scheme outperforms the unweighted naive solution. Computer simulations show that the proposed method achieves higher estimation accuracy as compared to an existing greedy-based algorithm. [ABSTRACT FROM AUTHOR]

The generalized Orthogonal Matching Pursuit (gOMP) algorithm generalizes the OMP algorithm by selecting more than one atom in each iteration. Under conventional settings, the gOMP algorithm iterates K loops where K is the sparsity of the sparse signal that is to be recovered. Thus, K is usually unknown beforehand. We propose stopping rules along with sufficient conditions for the gOMP algorithm to recover the whole or a part of the sparse signal support from noisy observations. It is proved that under conditions on restricted isometry constant (RIC) and magnitude of nonzero elements of the sparse signal, the gOMP algorithm will recover the support with given stopping rules under various noisy settings. We also give conditions under which partial support corresponding to components with significant magnitude of the sparse signal can be recovered. [ABSTRACT FROM AUTHOR]

We investigate the minimal number of linear measurements needed to recover sparse disjointed vectors robustly in the presence of measurement error. First, we analyze an iterative hard thresholding algorithm relying on a dynamic program computing sparse disjointed projections to upper-bound the order of the minimal number of measurements. Next, we show that this order cannot be reduced by any robust algorithm handling noninflating measurements. As a consequence, we conclude that there is no benefit in knowing the simultaneity of sparsity and disjointedness over knowing only one of these structures. [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]

Greed is good. However, the tighter you squeeze, the less you have. In this paper, a less greedy algorithm for sparse signal reconstruction in compressive sensing, named orthogonal matching pursuit with thresholding is studied. Using the global 2-coherence, which provides a “bridge” between the well known mutual coherence and the restricted isometry constant, the performance of orthogonal matching pursuit with thresholding is analyzed and more general results for sparse signal reconstruction are obtained. It is also shown that given the same assumption on the coherence index and the restricted isometry constant as required for orthogonal matching pursuit, the thresholding variation gives exactly the same reconstruction performance with significantly less complexity. [ABSTRACT FROM PUBLISHER]

The aim of this article is to construct the generalized random matrices, which satisfies the restricted isometry property (as introduced by Candes and Tao). Let the data be presented as a product of a vector with not more than K nonzero coordinates by a given matrix. We show that for such data we can change the upper bound of the variable K. In particular, we prove that the random matrices whose entries are independent realizations of random variables from φ-subgaussian space could be used in the theory of compressive sensing for encoding vectors. [ABSTRACT FROM AUTHOR]

The aim of this article is to construct the generalized random matrices, which satisfies the restricted isometry property (as introduced by Candes and Tao). Let the data be presented as a product of a vector with not more than K nonzero coordinates by a given matrix. We show that for such data we can change the upper bound of the variable K. In particular, we prove that the random matrices whose entries are independent realizations of random variables from φ-subgaussian space could be used in the theory of compressive sensing for encoding vectors. [ABSTRACT FROM AUTHOR]

In this paper, we propose a detector, based on the compressive sensing (CS) principles, for multiple-access spatial modulation (SM) channels with a large-scale antenna base station (BS). Particularly, we exploit the use of a large number of antennas at the BSs and the structure and sparsity of the SM transmitted signals to improve the performance of conventional detection algorithms. Based on the above, we design a CS-based detector that allows the reduction of the signal processing load at the BSs particularly pronounced for SM in large-scale multiple-input–multiple-output (MIMO) systems. We further carry out analytical performance and complexity studies of the proposed scheme to evaluate its usefulness. The theoretical and simulation results presented in this paper show that the proposed strategy constitutes a low-complexity alternative to significantly improve the system's energy efficiency against conventional MIMO detection in the multiple-access channel. [ABSTRACT FROM AUTHOR]

In Compressive Sensing, the Restricted Isometry Property (RIP) ensures that robust recovery of sparse vectors is possible from noisy, undersampled measurements via computationally tractable algorithms. It is by now well-known that Gaussian (or, more generally, sub-Gaussian) random matrices satisfy the RIP under certain conditions on the number of measurements. Their use can be limited in practice, however, due to storage limitations, computational considerations, or the mismatch of such matrices with certain measurement architectures. These issues have recently motivated considerable effort towards studying the RIP for structured random matrices. In this paper, we study the RIP for block diagonal measurement matrices where each block on the main diagonal is itself a sub-Gaussian random matrix. Our main result states that such matrices can indeed satisfy the RIP but that the requisite number of measurements depends on certain properties of the basis in which the signals are sparse. In the best case, these matrices perform nearly as well as dense Gaussian random matrices, despite having many fewer nonzero entries. [ABSTRACT FROM AUTHOR]

The success of compressed sensing relies essentially on the ability to efficiently find an approximately sparse solution to an under-determined linear system. In this paper, we developed an efficient algorithm for the sparsity promoting \ell^1-regularized least squares problem by coupling the primal dual active set strategy with a continuation technique (on the regularization parameter). In the active set strategy, we first determine the active set from primal and dual variables, and then update the primal and dual variables by solving a low-dimensional least square problem on the active set, which makes the algorithm very efficient. The continuation technique globalizes the convergence of the algorithm, with provable global convergence under restricted isometry property (RIP). Further, we adopt two alternative methods, i.e., a modified discrepancy principle and a Bayesian information criterion, to choose the regularization parameter automatically. Numerical experiments indicate that our algorithm is very competitive with state-of-the-art algorithms in terms of accuracy and efficiency, without a priori information about the regularization parameter. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the problem of determining the conditions under which the restricted isometry property (RIP) is satisfied for a particular type of matrix referred to in here as a banded random matrix (BRM). Such matrices have been recognized as suitable models for a number of compressive-sensing based sampling architectures, including the interleaved random demodulator, the random demodulator, the parallel non-interleaved random demodulator, the random sampler, and the periodic nonuniform sampler. It is thus important to establish the conditions under which the BRM satisfies the RIP; to our knowledge, this question has not been theoretically addressed in the literature. If the resulting conditions are satisfied, full signal recovery using a convex optimization algorithm is guaranteed. The specific objective of this research is to determine the conditions under which the RIP is satisfied for two possible sampling matricies: a BRM and a BRM multiplied by the discrete Fourier matrix. [ABSTRACT FROM PUBLISHER]

We consider two theorems from the theory of compressive sensing. Mainly a theorem concerning uniform recovery of random sampling matrices, where the number of samples needed in order to recover an s-sparse signal from linear measurements (with high probability) is known to be m~\gtrsim~s(\ln s)^3\ln N. We present new and improved constants together with what we consider to be a more explicit proof. A proof that also allows for a slightly larger class of m\times N-matrices, by considering what is called effective sparsity. We also present a condition on the so-called restricted isometry constants, \deltas, ensuring sparse recovery via \ell^1-minimization. We show that \delta2s<4/\sqrt{41} is sufficient and that this can be improved further to almost allow for a sufficient condition of the type \delta2s<2/3. [ABSTRACT FROM AUTHOR]

Abstract: Minimizing the -seminorm of a vector under convex constraints is a combinatorial (NP-hard) problem. Replacement of the -seminorm with the -norm is a commonly used approach to compute an approximate solution of the original -minimization problem by means of convex programming. In the theory of compressive sensing, the condition that the sensing matrix satisfies the Restricted Isometry Property (RIP) is a sufficient condition to guarantee that the solution of the -approximated problem is equal to the solution of the original -minimization problem. However, the evaluation of the conservativeness of the -relaxation approaches is recognized to be a difficult task in case the RIP is not satisfied. In this paper, we present an alternative approach to minimize the -norm of a vector under given constraints. In particular, we show that an -minimization problem can be relaxed into a sequence of semidefinite programming problems, whose solutions are guaranteed to converge to the optimizer (if unique) of the original combinatorial problem also in case the RIP is not satisfied. Segmentation of ARX models is then discussed in order to show, through a relevant problem in system identification, that the proposed approach outperforms the -based relaxation in detecting piece-wise constant parameter changes in the estimated model. [Copyright &y& Elsevier]

Since compressive sensing deals with a signal reconstruction using a reduced set of measurements, the existence of a unique solution is of crucial importance. The most important approach to this problem is based on the restricted isometry property which is computationally unfeasible. The coherence index-based uniqueness criteria are computationally efficient, however, they are pessimistic. An approach to alleviating this problem has been recently introduced by relaxing the coherence index condition for the unique signal reconstruction using the orthogonal matching pursuit approach. This approach can be further relaxed and the sparsity bound improved if we consider only the solution existence rather than its reconstruction. One such improved bound for the sparsity limit is derived in this paper using the Gershgorin disk theorem. [ABSTRACT FROM AUTHOR]

Theoretical analysis of randomized, compressive operators often depends on a concentration of measure inequality for the operator in question. Typically, such inequalities quantify the likelihood that a random matrix will preserve the norm of a signal after multiplication. Concentration of measure results are well established for unstructured compressive matrices, populated with independent and identically distributed (i.i.d.) random entries. Many real-world acquisition systems, however, are subject to architectural constraints that make such matrices impractical. In this paper we derive concentration of measure bounds for two types of block diagonal compressive matrices, one in which the blocks along the main diagonal are random and independent, and one in which the blocks are random but equal. For both types of matrices, we show that the likelihood of norm preservation depends on certain properties of the signal being measured, but that for the best case signals, both types of block diagonal matrices can offer concentration performance on par with their unstructured, i.i.d. counterparts. We support our theoretical results with illustrative simulations as well as analytical and empirical investigations of several signal classes that are highly amenable to measurement using block diagonal matrices. We also discuss applications of these results in ensuring stable embeddings for various signal families and in establishing performance guarantees for solving various signal processing tasks (such as detection and classification) directly in the compressed domain. [ABSTRACT FROM AUTHOR]

Abstract: Iterative hard thresholding (IHT) is a class of effective methods to compute sparse solution for underdetermined linear system. In this paper, an efficient IHT method with theoretical guarantee is proposed and named SCIHTBB with attractive features: (1) Monotone and Non-Monotone versions are presented with initial Barzilai–Borwein step size and finite step line search. (2) Convergence analysis has been developed based on the asymmetrical restricted isometry property. (3) An adaptive sparsity framework is provided to tackle the problem with unknown sparsity. (4) Some extensions are presented to handle group sparsity, non-negative sparsity and matrix rank minimization. Experimental comparisons with some state of the art methods verify that SCIHTBB is faster and more accurate for compressive sensing and matrix completion. [Copyright &y& Elsevier]

The emerging theory of compressive or compressed sensing challenges the convention of modern digital signal processing by establishing that exact signal reconstruction is possible for many problems where the sampling rate falls well below the Nyquist limit. Following the landmark works of Candës et al. and Donoho on the performance of l1 -minimization models for signal reconstruction, several authors demonstrated that certain nonconvex reconstruction models consistently outperform the convex l1 -model in practice at very low sampling rates despite the fact that no global minimum can be theoretically guaranteed. Nevertheless, there has been little theoretical investigation into the performance of these nonconvex models. In this paper, a notion of weak signal recoverability is introduced and the performance of nonconvex reconstruction models employing general concave metric priors is investigated under this model. The sufficient conditions for establishing weak signal recoverability are shown to substantially relax as the prior functional is parameterized to more closely resemble the targeted l0-model, offering new insight into the empirical performance of this general class of reconstruction methods. Examples of relaxation trends are shown for several different prior models. [ABSTRACT FROM AUTHOR]

We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of linear programming (LP) optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean-squared error of the reconstruction is upper-bounded by constant multiples of the measurement and signal perturbation energies. [ABSTRACT FROM AUTHOR]

Reflectometry techniques for water pipeline defect detection suffer from low resolution problems since only low frequency waves can travel long distances in pipeline systems. In this paper, a method for estimating the super-resolved impulse response (IR) of the system from reflectometry measurements is established using a gridless compressive sensing (CS) framework. The proposed method provides super-resolution results by reconstructing the sparse IR consisting of a series of delta (δ) functions, whose time delays and amplitudes are estimated by solving the dual problem of CS optimization. The unique reconstruction of IR is guaranteed by a minimum separation between adjacent δ functions, which closely relates to IR sparsity. This minimum separation requirement is validated theoretically, using the restricted isometry property, and numerically. It is proven that the IR of two discrete defects spaced less than a quarter of the minimum observation wavelength can be uniquely reconstructed with super-resolution. Systematic simulations and laboratory experiments show that the proposed method precisely recovers the IR of uniform blockages and leakages in water pipelines when the minimum separation is satisfied. With super-resolution IR, closely spaced blockage edges and leakages can be well distinguished and precisely localized. The size of both blockages and leakage holes can also be estimated with millimeter level accuracy. [ABSTRACT FROM AUTHOR]

Compressive sensing (CS) is well-known for its unique functionalities of sensing, compressing, and security (i.e. equal importance of CS measurements). However, there is a tradeoff. Improving sensing and compressing efficiency with prior signal information tends to favour particular measurements, thus decreasing security. This work aimed to improve the sensing and compressing efficiency without compromising security with a novel sampling matrix, named Restricted Structural Random Matrix (RSRM). RSRM unified the advantages of frame-based and block-based sensing together with the global smoothness prior (i.e. low-resolution signals are highly correlated). RSRM acquired compressive measurements with random projection of multiple randomly sub-sampled signals, which was restricted to low-resolution signals (equal in energy), thereby its observations are equally important. RSRM was proven to satisfy the Restricted Isometry Property and showed comparable reconstruction performance with recent state-of-the-art compressive sensing and deep learning-based methods. • Propose a novel sampling matrix that improves the sampling efficiency without scarifying the democracy. • Combine partial sampling, multi-images super-resolution, coded imaging, and compressive sensing. • Proposed matrix satisfies the Restricted Isometry Property with competitive reconstruction performance. [ABSTRACT FROM AUTHOR]

• Optimal sensor arrangement is treated for the identification of sound source with the compressive sensing. • Objective function is established with the use of the Restricted Isometry Property. • The proposed method enhances the array performance for low frequency- and/or SNR-environment. This paper adopts the theory of compressive sensing (CS) for the identification of sound source with attention on the sensor arrangement in the random array. As a lower Restricted Isometry Constant (RIC) is anticipated for satisfying the Restricted Isometry Property (RIP) that assures a stable recovery with CS, an objective function is established with the RIC averaging over the array's intended frequency range. Monte-Carlo based statistical method enables an estimation of RIC in the course of the minimization process, thereby proper sensor positions could be determined. The demonstration through numerical simulations and experimental measurements examines an optimal arrangement of 24 sensors for a given aperture, which is compared to two different types of random arrays. It is shown that the sensor configuration obtained by the proposed approach offers an improved performance as the frequency decreases and/or signal-to-noise ratio gets worse. [ABSTRACT FROM AUTHOR]