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]

We propose the Rescaled Matching Pursuit (RMP) algorithm to recover sparse signals in high-dimensional Euclidean spaces. The RMP algorithm has less computational complexity than other greedy-type algorithms, such as Orthogonal Matching Pursuit (OMP). We show that if the restricted isometry property is satisfied, then the upper bound of the error between the original signal and its approximation can be derived. Furthermore, we prove that the RMP algorithm can find the correct support of sparse signals from random measurements with a high probability. Our numerical experiments also verify this conclusion and show that RMP is stable with the noise. So, the RMP algorithm is a suitable method for recovering sparse signals. [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]

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]

We introduce a novel iterative algorithm, termed the Heavy-Ball-Based Hard Thresholding Pursuit for sparse phase retrieval problem (SPR-HBHTP), to reconstruct a sparse signal from a small number of magnitude-only measurements. Our algorithm is obtained via a natural combination of the Hard Thresholding Pursuit for sparse phase retrieval (SPR-HTP) and the classical Heavy-Ball (HB) acceleration method. The robustness and convergence for the proposed algorithm were established with the help of the restricted isometry property. Furthermore, we prove that our algorithm can exactly recover a sparse signal with overwhelming probability in finite steps whenever the initialization is in the neighborhood of the underlying sparse signal, provided that the measurement is accurate. Extensive numerical tests show that SPR-HBHTP has a markedly improved recovery performance and runtime compared to existing alternatives, such as the Hard Thresholding Pursuit for sparse phase retrieval problem (SPR-HTP), the SPARse Truncated Amplitude Flow (SPARTA), and Compressive Phase Retrieval with Alternating Minimization (CoPRAM). [ABSTRACT FROM AUTHOR]

Two-dimensional (2D) compressive beamforming (CB) with planar microphone array for acoustic source identification has attracted much attention due to its advantages of wide identification space, applicability to both coherent and incoherent acoustic sources, and clear imaging. It realizes acoustic source identification by establishing and solving the underdetermined equations between the sound pressure measured by the microphone array and the source strengths of the discretized grid points in the target area. Convex relaxation algorithms and greedy algorithms are often used to solve these underdetermined equations. CB based on convex relaxation requires the sensing matrix to satisfy the restricted isometry property and needs large calculating consumption, which is unsuitable for large-scale problems. CB based on greedy algorithms may achieve a locally optimal solution instead of the global optimum, and it is easily affected by the coherence of the sensing matrix columns, so its performance is sensitive to the grid spacing. To take into account both the robustness of acoustic source identification performance and high computational efficiency, we adapted sparse Bayesian learning (SBL) to solve the above underdetermined equations and proposed a 2D-SBL-CB in this paper. It first assumes the signal prior and noise prior to derive the posterior probability distribution of the source strength, and then adaptively estimates the hyperparameters of the sparse prior of source strength based on a type-II maximum likelihood, i.e., by maximizing the evidence, to achieve source identification. Both simulations and experiment show that the proposed 2D-SBL-CB is robust to grid spacing and has stable source identification performance. It also enjoys high computational efficiency, strong spatial resolution ability, and strong anti-noise interference, with optimal overall performance. [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]

This paper considers the orthogonal observation matrix design of deterministic compressive sampling (CS). An observation matrix called the weighted truncated Hadamard-modulated wideband converter (WITH-MWC) is deterministically designed based on the truncated Hadamard matrix. This matrix can meet the restricted isometry property (RIP) condition with overwhelming probability by randomly or strategically extracting from a standard Hadamard matrix. Most compressed sampling systems are highly sensitive to noise. To reduce the adverse effects of noise interference, partial specific matrix elements are weighted according to the sparse characteristics of multiband signals, and the recovery probability is provably better than that of the original system and other deterministic observation matrices, especially in the low signal-to-noise ratio scenario. Compared to the random Gaussian and random Bernoulli matrices, WITH-MWC is much easier to implement in hardware. The simulations verify the above analysis. [ABSTRACT FROM AUTHOR]

In this work, we study the performance of sub-gradient method (SubGM) on a natural nonconvex and nonsmooth formulation of low-rank matrix recovery with l1-loss, where the goal is to recover a low-rank matrix from a limited number of measurements, a subset of which may be grossly corrupted with noise. We study a scenario where the rank of the true solution is unknown and over-estimated instead. The over-estimation of the rank gives rise to an over-parameterized model in which there are more degrees of freedom than needed. Such over-parameterization may lead to overfitting, or adversely affect the performance of the algorithm. We prove that a simple SubGM with small initialization is agnostic to both over-parameterization and noise in the measurements. In particular, we show that small initialization nullifies the effect of over-parameterization on the performance of SubGM, leading to an exponential improvement in its convergence rate. Moreover, we provide the first unifying framework for analyzing the behavior of SubGM under both outlier and Gaussian noise models, showing that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values, and, perhaps surprisingly, even if the globally optimal solutions do not correspond to the ground truth. At the core of our results is a robust variant of restricted isometry property, called Sign-RIP, which controls the deviation of the sub-differential of the l1-loss from that of an ideal, expected loss. As a byproduct of our results, we consider a subclass of robust low-rank matrix recovery with Gaussian measurements, and show that the number of required samples to guarantee the global convergence of SubGM is independent of the over-parameterized rank.1 [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]

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]

In this paper, we generalize the conditions for the exact or stable recovery of weighted k-sparse signals in weighted sparse phase retrieval in our previous work [11] from the weighted ℓ1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\ell _1$$\end{document} minimization to the weighted ℓq(0k-sparse signal from its noiseless phaseless measurements via the weighted ℓq(0k-sparse signal from its noisy phaseless measurements via the weighted ℓq(0

In practical engineering scenarios, constraints arising from sensor placement, quantity, and the limitations of current testing technologies often lead to turbulence data characterized by low resolution and irregular structures. Turbulence super-resolution reconstruction is crucial for extracting finer details from irregularly structured, low-resolution measurement data, thereby facilitating comprehensive flow field analyses. This article introduces a sparse learning model (Embedding Restricted Isometry Property Autoencoder (RIP-AE)) for achieving super-resolution reconstruction of flow fields by obtaining compressed representations and sparse transform domain information. In this model, we embed the Restricted Isometry Property (RIP) condition to ensure the effectiveness of compressed representations and sparse transform domains, thereby enhancing the super-resolution reconstruction accuracy of the model. To assess the performance of the RIP-AE model, we utilized data sets of flow around a cylinder at different Reynolds numbers generated by unsteady Reynolds-Averaged Navier–Stokes simulations. We sequentially validate the effectiveness of the RIP condition at different Reynolds numbers (ranging from 1,000 to 500,000) and compare the reconstruction results of the RIP-AE model with those of the downsampled skip-connection/multi-scale (DSC/MS) and MS-AE models under different sampling ratios. The results indicate that the RIP-AE model excels in terms of L2 relative error and demonstrates the capability to achieve high-precision flow field reconstruction even under high sampling ratios. [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]

In this paper, the ℓ 1 -analysis model for the phase retrieval problem of sparse unknown signals in the redundant dictionary is extended to the ℓ p -analysis model, where 0 < p ≤ 1. It's shown that if the measurement matrix A satisfies the strong restricted isometry property adapted to D (S-DRIP) condition, the unknown signal x can be stably recovered by analyzing the ℓ p (0 < p ≤ 1) minimization model. [ABSTRACT FROM AUTHOR]

Motivated by the emerging role of interpolating machines in signal processing and machine learning, this work considers the computational aspects of over-parametrized matrix factorization. In this context, the optimization landscape may contain spurious stationary points (SSPs), which are proved to be full-rank matrices. The presence of these SSPs means that it is impossible to hope for any global guarantees in over-parametrized matrix factorization. For example, when initialized at an SSP, the gradient flow will be trapped there forever. Nevertheless, despite these SSPs, we establish in this work that the gradient flow of the corresponding merit function converges to a global minimizer, provided that its initialization is rank-deficient and sufficiently close to the feasible set of the optimization problem. We numerically observe that a heuristic discretization of the proposed gradient flow, inspired by primal-dual algorithms, is successful when initialized randomly. Our result is in sharp contrast with the local refinement methods which require an initialization close to the optimal set of the optimization problem. More specifically, we successfully avoid the traps set by the SSPs because the gradient flow remains rank-deficient at all times, and not because there are no SSPs nearby. The latter is the case for the local refinement methods. Moreover, the widely-used restricted isometry property plays no role in our main result. [ABSTRACT FROM AUTHOR]

The task of recovering a low-rank matrix from its noisy linear measurements plays a central role in computational science. Smooth formulations of the problem often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension of the ambient space. In contrast, we here show that in a variety of concrete circumstances, nonsmooth penalty formulations do not suffer from the same type of ill-conditioning. Consequently, standard algorithms for nonsmooth optimization, such as subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. Moreover, nonsmooth formulations are naturally robust against outliers. Our framework subsumes such important computational tasks as phase retrieval, blind deconvolution, quadratic sensing, matrix completion, and robust PCA. Numerical experiments on these problems illustrate the benefits of the proposed approach. [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]

A complete characterization for the restricted isometry constant (RIC) bounds on $\delta _{{{ tk}}}$ for all $ {t}>0$ is an important problem on recovery of sparse signals with prior support information via weighted $\ell _{{p}}$ -minimization ($0 < {p} \leqslant 1$). In this paper, new bounds on the restricted isometry constants $\delta _{{{ tk}}}$ ($0 < {t} < \frac {4}{3}{d}$), where $d$ is a key constant determined by prior support information, are established to guarantee the sparse signal recovery via the weighted $\ell _{{p}}$ minimization in both noiseless and noisy settings. This result fills a vacancy on $\delta _{{{ tk}}}$ with $0 < {t} < \frac {4}{3}{d}$ , compared with previous works on $\delta _{{{ tk}}}$ (${t} \geqslant \frac {4}3{d}$). We show that, when the accuracy of prior support estimate is at least 50%, the new recovery condition in terms of $\delta _{{{ tk}}}$ ($0 < {t} < \frac {4}{3}{d}$) via weighted $\ell _{1}$ minimization is weaker than the condition required by classical $\ell _{1}$ minimization without weighting. Our weighted $\ell _{1}$ minimization gives better recovery error bounds in noisy setting. Similarly, the new recovery condition in terms of $\delta _{{{ tk}}}$ ($0 < {t} < \frac {4}{3}{d}$) is extended to weighted $\ell _{{p}}$ ($0 < {p} < 1$) minimization, and it is also weaker than the condition obtained by standard non-convex $\ell _{{p}}$ ($0 < {p} < 1$) minimization without weighting. Numerical illustrations are provided to demonstrate our new theoretical results. [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]

For recovering block-sparse signals with unknown block structures using compressive sensing, a block orthogonal matching pursuit- (BOMP-) like block generalized orthogonal matching pursuit (BgOMP) algorithm has been proposed recently. This paper focuses on support conditions of recovery of any K -sparse block signals incorporating BgOMP under the framework of restricted isometry property (RIP). The proposed support conditions guarantee that BgOMP can achieve accurate recovery block-sparse signals within k iterations. [ABSTRACT FROM AUTHOR]

Low-rank matrix estimation plays a central role in various applications across science and engineering. Recently, nonconvex formulations based on matrix factorization are provably solved by simple gradient descent algorithms with strong computational and statistical guarantees. However, when the low-rank matrices are asymmetric, existing approaches rely on adding a regularization term to balance the scale of the two matrix factors which in practice can be removed safely without hurting the performance when initialized via the spectral method. In this paper, we provide a theoretical justification to this for the matrix sensing problem, which aims to recover a low-rank matrix from a small number of linear measurements. As long as the measurement ensemble satisfies the restricted isometry property, gradient descent—in conjunction with spectral initialization—converges linearly without the need of explicitly promoting balancedness of the factors; in fact, the factors stay balanced automatically throughout the execution of the algorithm. Our analysis is based on analyzing the evolution of a new distance metric that directly accounts for the ambiguity due to invertible transforms, and might be of independent interest. [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]

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]

Text classification plays an important role in various applications of big data by automatically classifying massive text documents. However, high dimensionality and sparsity of text features have presented a challenge to efficient classification. In this paper, we propose a compressive sensing- (CS-) based model to speed up text classification. Using CS to reduce the size of feature space, our model has a low time and space complexity while training a text classifier, and the restricted isometry property (RIP) of CS ensures that pairwise distances between text features can be well preserved in the process of dimensionality reduction. In particular, by structural random matrices (SRMs), CS is free from computation and memory limitations in the construction of random projections. Experimental results demonstrate that CS effectively accelerates the text classification while hardly causing any accuracy loss. [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 put forth a new joint sparse recovery algorithm called signal space matching pursuit (SSMP). The key idea of the proposed SSMP algorithm is to sequentially investigate the support of jointly sparse vectors to minimize the subspace distance to the residual space. Our performance guarantee analysis indicates that SSMP accurately reconstructs any row K-sparse matrix of rank r in the full row rank scenario if the sampling matrix $\mathbf {A}$ satisfies $\mathop{\mathrm{krank}}\limits (\mathbf {A}) \ge {K}+1$ , which meets the fundamental minimum requirement on $\mathbf {A}$ to ensure exact recovery. We also show that SSMP guarantees exact reconstruction in at most ${K}-{r}+\lceil \frac {{r}}{{L}} \rceil $ iterations, provided that $\mathbf {A}$ satisfies the restricted isometry property (RIP) of order ${L}({K}-{r})+{r}+1$ with $\delta _{{L}({K}-{r})+{r}+1} < \max \left \{{ \frac {\sqrt {{r}}}{\sqrt {{K}+\frac {{r}}{4}}+\sqrt {\frac {{r}}{4}}}, \frac {\sqrt {{L}}}{\sqrt {K}+1.15 \sqrt {{L}}} }\right \}$ , where L is the number of indices chosen in each iteration. This implies that the requirement on the RIP constant becomes less restrictive when r increases. Such behavior seems to be natural but has not been reported for most of conventional methods. We also show that if ${r}=1$ , then by running more than K iterations, the performance guarantee of SSMP can be improved to $\delta _{\lfloor 7.8{K} \rfloor } \le 0.155$. Furthermore, we show that under a suitable RIP condition, the reconstruction error of SSMP is upper bounded by a constant multiple of the noise power, which demonstrates the robustness of SSMP to measurement noise. Finally, from extensive numerical experiments, we show that SSMP outperforms conventional joint sparse recovery algorithms both in noiseless and noisy scenarios. [ABSTRACT FROM AUTHOR]

Compressive spectral imaging (CSI) sensors allow the acquisition of spatial and spectral data using a set of coded projections. The single pixel camera (SPC) is a low-cost CSI architecture capable of sensing high-resolution spectral images, whose potential is diminished by its slow acquisition time due to the large number of required projections. To partially alleviate this issue, dual arm optical systems have been designed such that side information of the scene is captured to guide the reconstruction process. To fully exploit the capabilities of the dual system, the SPC sensing matrix, or equivalently the coding patterns; should be properly designed. Therefore, this work proposes an optimized sensing matrix design for the SPC based on a super-pixel map of the scene, obtained from the side information, such that the number of projections is drastically reduced while the reconstruction quality is improved. Indeed, theoretical analysis based on the restricted isometry property indicates that the error of the reconstruction vanishes when the SPC uses the designed sensing matrix. Simulation and experimental results show that the proposed sensing matrix design improves the reconstruction quality. Specifically, the proposed approach improves image quality in up to 15dB compared with the state of the art sensing matrix designs. Moreover, a fast multi-resolution reconstruction approach is proposed based on the designed matrix, which reduces computation time by two orders of magnitude and does not require an iterative process. [ABSTRACT FROM AUTHOR]

To avoid decorrelation, conventional synthetic aperture radar interferometry (InSAR) requires that interferometric images should have a common spectral band and the same resolution after proper preprocessing. For a high-resolution (HR) image and a low-resolution (LR) one, the interferogram quality is limited by the LR one since the non-common band (NCB) between two images is usually discarded. In this article, we try to establish an InSAR method to improve interferogram quality by means of exploiting the NCB. To this end, we first define a new interferogram, which has the same resolution as the HR image. Then we formulate the interferometric relationship between the two images into a compressive sensing (CS) model, which contains the proposed HR interferogram. With the sparsity of interferogram in appropriate domains, we model the interferogram formation as a typical sparse recovery problem. Due to the speckle effect in coherent radar imaging, the sensing matrix of our CS model is inherently random. We theoretically prove that the sensing matrix satisfies restricted isometry property, and thus the interferogram recovery performance is guaranteed. Furthermore, we provide a fast interferogram formation algorithm by exploiting computationally efficient structures of the sensing matrix. Numerical experiments show that the proposed method provides better interferogram quality in the sense of reduced phase noise and obtain extrapolated interferogram spectra with respect to CB processing. [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]

This paper considers recovery of matrices that are low rank or approximately low rank from linear measurements corrupted with additive noise. We study minimization of the difference of Nuclear and Frobenius norms (abbreviated as S 1 , 2 norm) as a nonconvex and Lipschitz continuous metric for solving this noisy low rank matrix recovery problem. We mainly study two types of bounded observation noisy low rank matrix recovery problems, including the l 2 -norm bounded noise and the Dantizg Selector noise. Based on the matrix restricted isometry property (abbreviated as M-RIP), we prove that this S 1 , 2 norm-based minimization method can stably recover a (approximately) low rank matrix in the two types bounded noisy low rank matrix recovery problems. In addition, we use the truncated difference of Nuclear and Frobenius norms (denoted as the truncated S 1 , 2 norm) to recover a low rank matrix when the observation noise is the Dantizg Selector noise. We give the stable recovery result for this truncated S 1 , 2 norm minimization in Dantizg Selector noise case when the linear measurement map satisfies the M-RIP condition. [ABSTRACT FROM AUTHOR]

A key issue in compressive sampling is to construct a sensing matrix that is stable and easy to design in hardware. In this paper, a novel chaotic sensing matrix is proposed by establishing a connection between sensing architecture and chaotic sinusoidal iterator. Based on a chaining method with the volumetric argument, we show that the proposed sinusoidal chaotic sensing matrix yields the well-known restricted isometry property. Numerical experiments with time-sparse signals and natural images are reported to compare the sampling performance between chaotic sensing constructions and random ones. The obtained results indicate that the proposed chaotic matrix is always able to exhibit similar or superior performance with respect to its counterparts. Moreover, the proposed construction can be easily implemented on the field-programmable gate array environment. Our framework may guide other researchers to extend the proposed method for other chaotic systems as well. [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 article, we investigate the privacy issues that arise from a new frame-based kernel analysis approach to reconstruct from frame coefficient erasures. We show that while an erasure recovery matrix is needed in addition to a decoding frame for a receiver to recover the erasures, the erasure recovery matrix can be designed in such a way that it protects the encoding frame. The set of such erasure recovery matrices is shown to be an open and dense subset of a certain matrix space. We present algorithms to construct concrete examples of encoding frame and erasure recovery matrix pairs for which the erasure reconstruction process is robust to additive channel noise. Using the Restricted Isometry Property, we also provide quantitative bounds on the amplification of sparse additive channel noise. Numerical experiments are presented on the amplification of additive normally distributed random channel noise. In both cases, the amplification factors are demonstrated to be quite small. [ABSTRACT FROM AUTHOR]

Millimeter-wave (mmWave) communications have attracted considerable interest due to the massive available spectrum. However, to establish communication links, a beam training procedure is indispensable. How to accelerate the beam training process is one of the key challenges towards realizing mmWave communications in practice. In this study, we first propose a novel low-cost digital beamforming (DBF) module assisted hybrid (DA-hybrid) architecture, by exploiting both the capabilities of analog and digital modules. To make this topology practical, we deploy coarse radio frequency (RF) chains and low-resolution analog-to-digital converters in the low-cost DBF module to reduce cost and power consumption. Second, we design a fast beam training method (named DAH-BT) by utilizing the proposed DA-hybrid architecture and leveraging the sparse nature of mmWave channels, in which an internal calibration method is adapted to obtain the parameters of the RF impairments and the orthogonal matching pursuit algorithm is utilized to estimate beams. We also prove that the developed measurement matrices satisfy the restricted isometry property. Extensive simulation results show that the DA-hybrid architecture can not only provide close to $\text{100}\%$ beam matching accuracy, but also dramatically reduce the system power consumption and cost. In addition, the proposed DAH-BT scheme consumes the shortest time for beam training over the state-of-art methods with comparable spectral efficiency. [ABSTRACT FROM AUTHOR]

We study the convolutional phase retrieval problem, of recovering an unknown signal $x \in \mathbb C^{n} $ from $m$ measurements consisting of the magnitude of its cyclic convolution with a given kernel $a \in \mathbb C^{m} $. This model is motivated by applications such as channel estimation, optics, and underwater acoustic communication, where the signal of interest is acted on by a given channel/filter, and phase information is difficult or impossible to acquire. We show that when $a$ is random and the number of observations $m$ is sufficiently large, with high probability $x$ can be efficiently recovered up to a global phase shift using a combination of spectral initialization and generalized gradient descent. The main challenge is coping with dependencies in the measurement operator. We overcome this challenge by using ideas from decoupling theory, suprema of chaos processes and the restricted isometry property of random circulant matrices, and recent analysis of alternating minimization methods. [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 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]

Millimeter wave (mmWave) systems can enable high data rates if the link between the transmitting and receiving radios is configured properly. Fast configuration of mmWave links, however, is challenging due to the use of large antenna arrays and hardware constraints. For example, a large amount of training overhead is incurred by exhaustive search-based beam alignment in typical mmWave phased arrays. In this paper, we present a framework called FALP for Fast beam Alignment with Low-resolution Phase shifters. FALP uses an efficient set of antenna weight vectors to acquire channel measurements, and allows faster beam alignment when compared to exhaustive scan. The antenna weight vectors in FALP can be realized in ultra-low power phase shifters whose resolution can be as low as one-bit. From a compressed sensing (CS) perspective, the CS matrix designed in FALP satisfies the restricted isometry property and allows CS algorithms to exploit the fast Fourier transform. The proposed framework also establishes a new connection between channel acquisition in phased arrays and magnetic resonance imaging. [ABSTRACT FROM AUTHOR]

The article explores how ultra-miniaturized microendoscopes are vital for numerous biomedical applications. Topics discussed include approach to microendoscopy which enabled by computational image recovery; using a single pseudorandom spatial mask at the distal end of amulticore fiber; and microendoscope demonstrates color resolved imaging and refocusing.

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]

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]

In this paper, we analyze the performance guarantee of the rank aware order recursive matching pursuit (RA-ORMP) algorithm in recovering a group of jointly sparse vectors. Specifically, we show that RA-ORMP accurately reconstructs any group of $r$ linearly independent jointly $K$ -sparse vectors, provided that the sampling matrix has unit $\ell _{2}$ -norm columns and satisfies the restricted isometry property (RIP) of order $K+1$ with $\delta _{K+1} < {\sqrt{r}} /\left({\sqrt{K+\frac{r}{4}}+\sqrt{\frac{r}{4}}}\right)$. We show the near-optimality of the proposed guarantee by providing a group of $r$ jointly $K$ -sparse vectors that cannot be recovered by RA-ORMP under $\delta _{K+1} \geq \sqrt{\frac{r}{K}}$. We also present a condition of RA-ORMP in the more realistic scenarios where a sampling matrix might not have unit $\ell _{2}$ -norm columns and the measurements are contaminated with noise. [ABSTRACT FROM AUTHOR]