Search

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]

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]

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]

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]

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

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

In sparse recovery, a sparse signal ${\mathbf x}\in \mathbb {R}^N$ with $K$ nonzero entries is to be reconstructed from a compressed measurement $\mathbf y=Ax$ with ${\mathbf A}\in \mathbb {R}^{M\times N}$ ($M

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]

Dimension reduction plays an essential role when decreasing the complexity of solving large-scale problems. The well-known Johnson-Lindenstrauss (JL) lemma and restricted isometry property (RIP) admit the use of random projection to reduce the dimension while keeping the Euclidean distance, which leads to the boom of compressed sensing and the field of sparsity related signal processing. Recently, successful applications of sparse models in computer vision and machine learning have increasingly hinted that the underlying structure of high dimensional data looks more like a union of subspaces. In this paper, motivated by JL lemma and an emerging field of compressed subspace clustering, we study for the first time the RIP of Gaussian random matrices for the compression of two subspaces based on the generalized projection F -norm distance. We theoretically prove that with high probability the affinity or distance between two projected subspaces are concentrated around their estimates. When the ambient dimension after projection is sufficiently large, the affinity and distance between two subspaces almost remain unchanged after random projection. Numerical experiments verify the theoretical work. [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]

In this paper, we consider multiuser detection that copes with multiple access interference caused in low-rate wireless communication systems with a large number of nodes, such as machine-to-machine communications. We take account of discreteness of transmitted signals (e.g., binary signals taking values of $\pm 1$), which we utilize as prior information in detection. We first formulate the detection problem as a maximum a posteriori estimation problem. Since this problem is highly nonconvex and discontinuous, we propose convex relaxation based on the sum-of-absolute-values (SOAV) optimization, which can be efficiently solved by proximal splitting. We also derive an upper bound of the relaxation error by the SOAV optimization in noisy cases based on the restricted isometry property. Numerical simulations are shown to illustrate the effectiveness of the proposed approach. [ABSTRACT FROM PUBLISHER]

Support recovery of sparse signals via orthogonal matching pursuit (OMP) has been extensively studied in recent years. In this paper, by exploiting the knowledge about orthogonal projection matrix and Schur complement, we study the sufficient conditions for exact support recovery of sparse signals with OMP in the framework of restricted isometry property (RIP). In the noisy case, we prove that under some constraints on the minimum magnitude of the nonzero elements of the K-sparse signal, OMP can exactly recover the support of the signal if the restricted isometry constant \delta K + 1 satisfies \delta K + 1 < {1 \mathord{/ {\vphantom {1 {\sqrt {K + 1} }}} } {\sqrt {K + 1} }}. Our constraints on the minimum magnitude of nonzero elements of the signal are weaker than existing ones. In the noiseless case, although it has been proved that \delta K + 1 < {1 \mathord{/ {\vphantom {1 {\sqrt {K + 1} }}} } {\sqrt {K + 1} }} is a sharp condition for exactly recovering any K-sparse signal with OMP, our result shows that under some constraints on the signal, OMP can also exactly recover the signal if \delta K + 1 satisfies \delta K + 1 < {{\sqrt 2 } \mathord{/ {\vphantom {{\sqrt 2 } 2}} } 2} . [ABSTRACT FROM PUBLISHER]

Support recovery of sparse signals from noisy measurements with orthogonal matching pursuit (OMP) has been extensively studied. In this paper, we show that for any K -sparse signal {\boldsymbol{x}} , if a sensing matrix \boldsymbol{A} satisfies the restricted isometry property (RIP) with restricted isometry constant \delta K+1 < 1/\sqrt{K+1}, then under some constraints on the minimum magnitude of nonzero elements of {\boldsymbol{x}} , OMP exactly recovers the support of \boldsymbolx from its measurements \boldsymboly=\boldsymbolA\boldsymbolx+\boldsymbolv in K iterations, where \boldsymbol{v} is a noise vector that is \ell _2 or \ell \infty bounded. This sufficient condition is sharp in terms of \delta K+1 since for any given positive integer K and any 1/\sqrt{K+1}\leq \delta <1, there always exists a matrix \boldsymbol{A} satisfying the RIP with \delta K+1=\delta for which OMP fails to recover a K-sparse signal \boldsymbolx in $K$ iterations. Also, our constraints on the minimum magnitude of nonzero elements of \boldsymbolx are weaker than existing ones. Moreover, we propose worst case necessary conditions for the exact support recovery of \boldsymbolx, characterized by the minimum magnitude of the nonzero elements of \boldsymbolx. [ABSTRACT FROM PUBLISHER]

In this paper, the joint support recovery of several sparse signals whose supports exhibit similarities is examined. Each sparse signal is acquired using the same noisy linear measurement process, which returns fewer observations than the dimension of the sparse signals. The measurement noise is assumed additive, Gaussian, and admits different variances for each sparse signal that is measured. Using the theory of compressed sensing, the performance of simultaneous orthogonal matching pursuit (SOMP) is analyzed for the envisioned signal model. The cornerstone of this paper is a novel analysis method upper bounding the probability that SOMP recovers at least one incorrect entry of the joint support during a prescribed number of iterations. Furthermore, the probability of SOMP failing is investigated whenever the number of sparse signals being recovered simultaneously increases and tends to infinity. In particular, convincing observations and theoretical results suggest that SOMP committing no mistake in the noiseless case does not guarantee the absence of error in the noisy case whenever the number of acquired sparse signals scales to infinity. Finally, simulation results confirm the validity of the theoretical results. [ABSTRACT FROM PUBLISHER]

In compressed sensing the matrices that satisfy the Restricted Isometry Property (RIP) play an important role. To date, however, very few results for designing such matrices are available. For applications such as multiplier-less data compression, binary sensing matrices are of interest. The present paper constructs deterministic and binary sensing matrices using Euler Squares. In particular, given a positive integer m different from p,{p}^{2} for a prime p , we show that it is possible to construct a binary sensing matrix of size mtimes c(mmu)^2, where mu is the coherence parameter of the matrix and $cin [1,2)$. The matrices that we construct have small density (that is, percentage of nonzero entries in the matrix is small) with no function evaluation in their construction, which support algorithms with low computational complexity. Through experimental work, we show that our binary sensing matrices can be used for such applications as content based image retrieval. Our simulation results demonstrate that the Euler Square based CS matrices give better performance than their Gaussian counterparts. [ABSTRACT FROM AUTHOR]

We consider a distributed compressed sensing scenario where many sensors measure correlated sparse signals and the sensors are connected through a network. Correlation between sparse signals is modeled by a partial common support-set. For such a scenario, the main objective of this paper is to develop a greedy pursuit algorithm. We develop a distributed parallel pursuit (dipp) algorithm based on exchange of information about estimated support-sets at sensors. The exchange of information helps to improve estimation of the partial common support-set, that in turn helps to gradually improve estimation of support-sets in all sensors, leading to a better quality reconstruction performance. We provide restricted isometry property (RIP) based theoretical analysis on the algorithm’s convergence and reconstruction performance. Under certain theoretical requirements (i.e., under certain assumptions) on the quality of information exchange over the network and RIP parameters of sensor nodes, we show that the dipp algorithm converges to a performance level that depends on a scaled additive measurement noise power (convergence in theory) where the scaling coefficient is a function of RIP parameters and information processing quality parameters. Using simulations, we show practical reconstruction performance of dipp vis-a-vis amount of undersampling, signal-to-measurement-noise ratios and network-connectivity conditions. [ABSTRACT FROM AUTHOR]

In compressive sensing (CS), the restricted isometry property (RIP) is an important condition on measurement matrices which guarantees the recovery of sparse signals with undersampled measurements. It has been proved in the prior works that both random (e.g., i.i.d. Gaussian, Bernoulli, \ldots) and Toeplitz matrices satisfy the RIP with high probability. However, structured matrices, such as banded Toeplitz matrices have drawn more attention since their structures have the advantage of fast matrix multiplication which may decrease the computational complexity of recovery algorithms. In this paper, we show that banded block Toeplitz matrices satisfy the RIP condition with high probability. Banded block Toeplitz matrices can be used in the sparse multi-channel source separation. The banded block Toeplitz matrices decrease the computational complexity while they have fewer number of non-zero entries in comparison to the same dimensional banded Toeplitz matrices. Furthermore, our simulation results show that banded block Toeplitz matrices outperform banded Toeplitz matrices in signal estimation. The analytical RIP bound for banded block Toeplitz matrices is provided in this paper and the RIP bound of sparse Gaussian matrices is also obtained as an upper bound for banded block Toeplitz matrices. Our simulation and analytical results show that sparse Gaussian random matrices do satisfy the RIP condition with high probability. The probability of satisfying the RIP depends on the probability of zero entries. [ABSTRACT FROM PUBLISHER]

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]

This paper focuses on the development of novel greedy techniques for distributed learning under sparsity constraints. Greedy techniques have widely been used in centralized systems due to their low computational requirements and at the same time their relatively good performance in estimating sparse parameter vectors/signals. The paper reports two new algorithms in the context of sparsity-aware learning. In both cases, the goal is first to identify the support set of the unknown signal and then to estimate the nonzero values restricted to the active support set. First, an iterative greedy multistep procedure is developed, based on a neighborhood cooperation strategy, using batch processing on the observed data. Next, an extension of the algorithm to the online setting, based on the diffusion LMS rationale for adaptivity, is derived. Theoretical analysis of the algorithms is provided, where it is shown that the batch algorithm converges to the unknown vector if a Restricted Isometry Property (RIP) holds. Moreover, the online version converges in the mean to the solution vector under some general assumptions. Finally, the proposed schemes are tested against recently developed sparsity-promoting algorithms and their enhanced performance is verified via simulation examples. [ABSTRACT FROM PUBLISHER]

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]

Quadrature sampling has been widely applied in coherent radar systems to extract in-phase and quadrature (I and Q) components in the received radar signal. However, the sampling is inefficient because the received signal contains only a small number of significant target signals. This paper incorporates the compressive sampling (CS) theory into the design of the quadrature sampling system, and develops a quadrature compressive sampling (QuadCS) system to acquire the I and Q components with low sampling rate. The QuadCS system first randomly projects the received signal into a compressive bandpass signal and then utilizes the quadrature sampling to output compressive I and Q components. The compressive outputs are used to reconstruct the I and Q components. To understand the system performance, we establish the frequency domain representation of the QuadCS system. With the waveform-matched dictionary, we prove that the QuadCS system satisfies the restricted isometry property with overwhelming probability. For K target signals in the observation interval T, simulations show that the QuadCS requires just \cal O(K\log(BT/K)) samples to stably reconstruct the signal, where B is the signal bandwidth. The reconstructed signal-to-noise ratio decreases by 3 dB for every octave increase in the target number K and increases by 3 dB for every octave increase in the compressive bandwidth. Theoretical analyses and simulations verify that the proposed QuadCS is a valid system to acquire the I and Q components in the received radar signals. [ABSTRACT FROM PUBLISHER]

Dimension reduction methods via linear random projections are used in numerous applications including data mining, information retrieval and compressive sensing (CS). While CS has traditionally relied on normal random projections, corresponding to \ell_2 distance preservation, a large body of work has emerged for applications where \ell_1 approximate distances may be preferred. Dimensionality reduction in \ell_1 often use Cauchy random projections that multiply the original data matrix \bf B\in \BBR^n\times D with a Cauchy random matrix \bf R\in\BBR^k\times n (k \ll n), resulting in a projected matrix \bf C \in\BBR^k\times D. In this paper, an analogous of the Restricted Isometry Property for dimensionality reduction in \ell_1 is proposed using explicit tail bounds for the geometric mean of the random projections. A set of signal reconstruction algorithms from the Cauchy random projections are then developed given that the large suite of reconstruction algorithms developed in compressive sensing perform poorly due to the lack of finite second-order statistics in the projections. These algorithms are based on regularized coordinate-descent Myriad estimates using both \ell_0 and Lorentzian norms as sparsity inducing terms. [ABSTRACT FROM PUBLISHER]

Orthogonal matching pursuit (OMP) is a greedy search algorithm popularly being used for the recovery of compressive sensed sparse signals. In this correspondence, we show that if the isometry constant \deltaK+1 of the sensing matrix \mmb\Phi satisfies \deltaK+1<{1\over\sqrt{K}+1} then the OMP algorithm can perfectly recover K-sparse signals from the compressed measurements \bf y=\mmb\Phi\bf x. Our bound offers a substantial improvement over the recent result of Davenport and Wakin and also closes gap between the recovery bound and fundamental limit over which the perfect recovery of the OMP cannot be guaranteed. [ABSTRACT FROM PUBLISHER]

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]

The stability of sparse signal reconstruction with respect to measurement noise is investigated in this paper. We design efficient algorithms to verify the sufficient condition for unique \ell1 sparse recovery. One of our algorithms produces comparable results with the state-of-the-art technique and performs orders of magnitude faster. We show that the \ell1-constrained minimal singular value (\ell1-CMSV) of the measurement matrix determines, in a very concise manner, the recovery performance of \ell1-based algorithms such as the Basis Pursuit, the Dantzig selector, and the LASSO estimator. Compared to performance analysis involving the Restricted Isometry Constant, the arguments in this paper are much less complicated and provide more intuition on the stability of sparse signal recovery. We show also that, with high probability, the subgaussian ensemble generates measurement matrices with \ell1-CMSVs bounded away from zero, as long as the number of measurements is relatively large. To compute the \ell1-CMSV and its lower bound, we design two algorithms based on the interior point algorithm and the semidefinite relaxation. [ABSTRACT FROM AUTHOR]

Takens' embedding theorem remarkably established that concatenating M previous outputs of a dynamical system into a vector (called a delay coordinate map) can be a one-to-one mapping of a low-dimensional attractor from the system state space. However, Takens' theorem is fragile in the sense that even small imperfections can induce arbitrarily large errors in this attractor representation. We extend Takens' result to establish deterministic, explicit and nonasymptotic sufficient conditions for a delay coordinate map to form a stable embedding in the restricted case of linear dynamical systems and observation functions. Our work is inspired by the field of Compressive Sensing (CS), where results guarantee that low-dimensional signal families can be robustly reconstructed if they are stably embedded by a measurement operator. However, in contrast to typical CS results, i) our sufficient conditions are independent of the size of the ambient state space, and ii) some system and measurement pairs have fundamental limits on the conditioning of the embedding (i.e., how close it is to an isometry), meaning that further measurements beyond some point add no further significant value. We use several simple simulations to explore the conditions of the main results, including the tightness of the bounds and the convergence speed of the stable embedding. We also present an example task of estimating the attractor dimension from time-series data to highlight the value of stable embeddings over traditional Takens' embeddings. [ABSTRACT FROM PUBLISHER]

In this paper, we present a concise and coherent analysis of the constrained l1 minimization method for stable recovering of high-dimensional sparse signals both in the noiseless case and noisy case. The analysis is surprisingly simple and elementary, while leads to strong results. In particular, it is shown that the sparse recovery problem can be solved via l1 minimization under weaker conditions than what is known in the literature. A key technical tool is an elementary inequality, called Shifting Inequality, which, for a given nonnegative decreasing sequence, bounds the l1 norm of a subsequence in terms of the l1 norm of another subsequence by shifting the elements to the upper end. [ABSTRACT FROM AUTHOR]

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]