Search

In this paper, we study an unconstrained l2,p minimization and its associated iteratively reweighted least squares algorithm (UBIRLS) for recovering block sparse signals. Wang et al. [Y. Wang, J. Wang and Z. Xu, On recovery of block-sparse signals via mixed l2/lq (0 < q ≤ 1) norm minimization, EURASIP J. Adv. Signal Process. 2013(76) (2013) 76] have used numerical experiments to show the remarkable performance of UBIRLS algorithm for recovering a block sparse signal, but no theoretical analysis such as convergence and convergence rate analysis of UBIRLS algorithm was given. We focus on providing convergence and convergence rate analysis of UBIRLS algorithm for block sparse recovery problem. First, the convergence of UBIRLS is proved strictly. Second, based on the block restricted isometry property (block RIP) of linear measurement matrix A, we give the error bound analysis of the UBIRLS algorithm. Lastly, we also characterize the local convergence behavior of the UBIRLS algorithm. The simplicity of UBIRLS algorithm, along with the theoretical guarantees provided in this paper, will make a compelling case for its adoption as a standard tool for block sparse recovery. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering elements of a low-dimensional model from under-determined linear measurements. To perform recovery, we consider the minimization of a convex regularizer subject to a data fit constraint. Given a model, we ask ourselves what is the 'best' convex regularizer to perform its recovery. To answer this question, we define an optimal regularizer as a function that maximizes a compliance measure with respect to the model. We introduce and study several notions of compliance. We give analytical expressions for compliance measures based on the best-known recovery guarantees with the restricted isometry property. These expressions permit to show the optimality of the |$\ell ^{1}$| -norm for sparse recovery and of the nuclear norm for low-rank matrix recovery for these compliance measures. We also investigate the construction of an optimal convex regularizer using the examples of sparsity in levels and of sparse plus low-rank models. [ABSTRACT FROM AUTHOR]

We provide high-probability bounds on the condition number of random feature matrices. In particular, we show that if the complexity ratio |$N/m$|⁠ , where |$N$| is the number of neurons and |$m$| is the number of data samples, scales like |$\log ^{-1}(N)$| or |$\log (m)$|⁠ , then the random feature matrix is well-conditioned. This result holds without the need of regularization and relies on establishing various concentration bounds between dependent components of the random feature matrix. Additionally, we derive bounds on the restricted isometry constant of the random feature matrix. We also derive an upper bound for the risk associated with regression problems using a random feature matrix. This upper bound exhibits the double descent phenomenon and indicates that this is an effect of the double descent behaviour of the condition number. The risk bounds include the underparameterized setting using the least squares problem and the overparameterized setting where using either the minimum norm interpolation problem or a sparse regression problem. For the noiseless least squares or sparse regression cases, we show that the risk decreases as |$m$| and |$N$| increase. The risk bound matches the optimal scaling in the literature and the constants in our results are explicit and independent of the dimension of the data. [ABSTRACT FROM AUTHOR]

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

The projected gradient method for matrix completion is generalized towards the higher-dimensional case of low-rank Tucker tensors. It is shown that an operation order rearrangement in the common projected gradient approach provides a complexity improvement. An even better algorithm complexity can be obtained by replacing the completion operator by a general operator that satisfies restricted isometry property; however, such a replacement transforms the completion algorithm into an approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper aims to study the performance of the amplitude-based model |$\widehat{{\boldsymbol x}} \in \mathop{\mathrm{argmin}}\limits _{{\boldsymbol x}\in \mathbb{C}^{d}}\sum _{j=1}^{m}\left (|\langle{\boldsymbol a}_{j},{\boldsymbol x}\rangle |-b_{j}\right)^{2}$|⁠ , where |$b_{j}:=|\langle{\boldsymbol a}_{j},{\boldsymbol x}_{0}\rangle |+\eta _{j}$| and |${\boldsymbol x}_{0}\in \mathbb{C}^{d}$| is a target signal. The model is raised in phase retrieval as well as in absolute value rectification neural networks. Many efficient algorithms have been developed to solve it in the past decades. However, there are very few results available regarding the estimation performance in the complex case under noisy conditions. In this paper, we present a theoretical guarantee on the amplitude-based model for the noisy complex phase retrieval problem. Specifically, we show that |$\min _{\theta \in [0,2\pi)}\|\widehat{{\boldsymbol x}}-\exp (\mathrm{i}\theta)\cdot{\boldsymbol x}_{0}\|_{2} \lesssim \frac{\|{\boldsymbol \eta }\|_{2}}{\sqrt{m}}$| holds with high probability provided the measurement vectors |${\boldsymbol a}_{j}\in \mathbb{C}^{d},$|   |$j=1,\ldots ,m,$| are i.i.d. complex sub-Gaussian random vectors and |$m\gtrsim d$|⁠. Here |${\boldsymbol \eta }=(\eta _{1},\ldots ,\eta _{m})\in \mathbb{R}^{m}$| is the noise vector without any assumption on the distribution. Furthermore, we prove that the reconstruction error is sharp. For the case where the target signal |${\boldsymbol x}_{0}\in \mathbb{C}^{d}$| is sparse, we establish a similar result for the nonlinear constrained |$\ell _{1}$| minimization model. To accomplish this, we leverage a strong version of restricted isometry property for an operator on the space of simultaneous low-rank and sparse matrices. [ABSTRACT FROM AUTHOR]

This paper considers the L 1 -minimization problem for sparse signal and image reconstruction by using projection neural networks (PNNs). Firstly, a new finite-time converging projection neural network (FtPNN) is presented. Building upon FtPNN, a new fixed-time converging PNN (FxtPNN) is designed. Under the condition that the projection matrix satisfies the Restricted Isometry Property (RIP), the stability in the sense of Lyapunov and the finite-time convergence property of the proposed FtPNN are proved; then, it is proven that the proposed FxtPNN is stable and converges to the optimum solution regardless of the initial values in fixed time. Finally, simulation examples with signal and image reconstruction are carried out to show the effectiveness of our proposed two neural networks, namely FtPNN and FxtPNN. [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]

The ratio of |$\ell _{1}$| and |$\ell _{2}$| norms, denoted as |$\ell _{1}/\ell _{2}$|⁠ , has presented prominent performance in promoting sparsity. By adding partial support information to the standard |$\ell _{1}/\ell _{2}$| minimization, in this paper, we introduce a novel model, i.e. the weighted |$\ell _{1}/\ell _{2}$| minimization, to recover sparse signals from the linear measurements. The restricted isometry property based conditions for sparse signal recovery in both noiseless and noisy cases through the weighted |$\ell _{1}/\ell _{2}$| minimization are established. And we show that the proposed conditions are weaker than the analogous conditions for standard |$\ell _{1}/\ell _{2}$| minimization when the accuracy of the partial support information is at least |$50\%$|⁠. Moreover, we develop effective algorithms and illustrate our results via extensive numerical experiments on synthetic data in both noiseless and noisy cases. [ABSTRACT FROM AUTHOR]

Recovery of sparse vectors and low-rank matrices from a small number of linear measurements is well-known to be possible under various model assumptions on the measurements. The key requirement on the measurement matrices is typically the restricted isometry property, that is, approximate orthonormality when acting on the subspace to be recovered. Among the most widely used random matrix measurement models are (a) independent subgaussian models and (b) randomized Fourier-based models, allowing for the efficient computation of the measurements. For the now ubiquitous tensor data, direct application of the known recovery algorithms to the vectorized or matricized tensor is memory-heavy because of the huge measurement matrices to be constructed and stored. In this paper, we propose modewise measurement schemes based on subgaussian and randomized Fourier measurements. These modewise operators act on the pairs or other small subsets of the tensor modes separately. They require significantly less memory than the measurements working on the vectorized tensor, provably satisfy the tensor restricted isometry property and experimentally can recover the tensor data from fewer measurements and do not require impractical storage. [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 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]

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

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

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

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 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]

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

The problem of completion of low-rank matrices is considered in a special setting, where each element of the matrix may be erroneous with a limited probability. Although such a perturbation is extremely sparse on a given mask of known elements, it is not incoherent and may cause instabilities in the commonly used projected gradient method. A new iterative method is proposed that is insensitive to rare observation errors and is more stable for ill-conditioned solutions. The method can also be used for finding a matrix approximation in the format of a sum of a low-rank and a sparse matrix. [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 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]

Recovery of low-rank matrices from a small number of linear measurements is now well-known to be possible under various model assumptions on the measurements. Such results demonstrate robustness and are backed with provable theoretical guarantees. However, extensions to tensor recovery have only recently began to be studied and developed, despite an abundance of practical tensor applications. Recently, a tensor variant of the Iterative Hard Thresholding method was proposed and theoretical results were obtained that exact guarantee recovery of tensors with low Tucker rank. In this paper, we utilize and prove a similar tensor version of the Restricted Isometry Property (RIP) to extend these results for tensors with low CANDECOMP/PARAFAC (CP) rank. In doing so, we leverage recent results on efficient approximations of CP decompositions that remove the need for challenging assumptions in prior works. We complement our theoretical findings with empirical results that showcase the potential of the approach. [ABSTRACT FROM AUTHOR]

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

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]

In this paper, two new sufficient conditions on stable recovery of the weighted signals via the weighted minimization are proposed based upon the weighted robust null space property (NSP) and the weighted restricted isometry property (RIP), respectively. Moreover, it is shown that the weighted RIP, as a stronger condition to estimate reconstruction errors, implies the weighted robust NSP. [ABSTRACT FROM AUTHOR]

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

We prove the Johnson-Lindenstrauss property for matrices ΦDξ, where Φ has the restricted isometry property and Dξ is a diagonal matrix containing the entries of a Kronecker product ξ=ξ(1)⊕...⊕ξ(d) of d independent Rademacher vectors. Such embeddings have been proposed in recent works for a number of applications concerning compression of tensor structured data, including the oblivious sketching procedure by Ahle et al. for approximate tensor computations. For preserving the norms of p points simultaneously, our result requires Φ to have the restricted isometry property for sparsity C(d)(logp)d. In the case of subsampled Hadamard matrices, this can improve the dependence of the embedding dimension on p to (logp)d while the best previously known result required (logp)d+1. That is, for the case of d=2 at the core of the oblivious sketching procedure by Ahle et al., the scaling improves from cubic to quadratic. We provide a counterexample to prove that the scaling established in our result is optimal under mild assumptions. [ABSTRACT FROM AUTHOR]

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

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

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

In this paper, several recurrent neural networks (RNNs) for solving the L 1 -minimization problem are proposed. First, a one-layer RNN based on the hyperbolic tangent function and the projection matrix is designed. In addition, the stability and global convergence of the previously presented RNN are proved by the Lyapunov method. Then, the sliding mode control technique is introduced into the former RNN to design finite-time RNN (FTRNN). Under the condition that the projection matrix satisfies the Restricted Isometry Property (RIP), a suitable Lyapunov function is constructed to prove that the FTRNN is stable in the Lyapunov sense and has the finite-time convergence property. Finally, we make a comparison of the proposed RNN and FTRNN with the existing RNNs. To achieve this, we implement experiments for sparse signal reconstruction and image reconstruction. The results further demonstrate the effectiveness and superior performance of the proposed RNN and FTRNN. [ABSTRACT FROM AUTHOR]

This note presents a unified analysis of the identification of dynamical systems with low-rank constraints under high-dimensional scaling. This identification problem for dynamic systems is challenging due to the intrinsic dependency of the data. To alleviate this problem, we first formulate this identification problem into a multivariate linear regression problem with a row-sub-Gaussian measurement matrix using the more general input designs and the independently repeated sampling schemes. We then propose a nuclear norm heuristic method that estimates the parameter matrix of a dynamic system from a few input-state data samples. Based on this, we can extend the existing results. In this article, we consider two scenarios. (i) In the noiseless scenario, nuclear-norm minimization is introduced for promoting low-rank. We define the notion of weak restricted isometry property, which is weaker than the ordinary restricted isometry property, and show it holds with high probability for the row-sub-Gaussian measurement matrix. Thereby, the rank-minimization matrix can be exactly recovered from a finite number of data samples. (ii) In the noisy scenario, a regularized framework involving the nuclear norm penalty is established. We give the notion of operator norm curvature condition for the loss function and show it holds for the row-sub-Gaussian measurement matrix with high probability. Consequently, when specifying the suitable choice of the regularization parameter, the operator norm error of the optimal solution of this program has a sharp bound given a finite amount of data samples. This operator norm error bound is always smaller than the ordinary Frobenius norm error bound obtained in the existing work. [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]

In this paper, we investigate the low-rank matrix recovery problem from linear observations. Inspired by the matrix Lasso and Dantzig selector, we propose nuclear norm regularized models with two data fitting items: ℓ 2 -loss function and Dantzig selector. We establish the recovery errors for both constrained and unconstrained models under the matrix restricted isometry property frame. For the unconstrained model, we obtain a tighter error bound compared with the previous study by W. Wang et al. (2021) under certain conditions. Furthermore, we design an effective solving algorithm for the proposed unconstrained model. Our numerical experiments demonstrate that our method outperforms the Lasso and Dantzig selector models. • Stable recovery errors for nuclear norm regularized models are established. • Efficient algorithm based on PSS method for low-rank matrix recovery is proposed. • Our method achieves good recovery performance in numerical experiments. [ABSTRACT FROM AUTHOR]

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

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

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

In this work, we study the optimization landscape of the non-convex matrix sensing problem that is known to have many local minima in the worst case. Since the existing results are related to the notion of restricted isometry property (RIP) that cannot directly capture the underlying structure of a given problem, they can hardly be applied to real-world problems where the amount of data is not exorbitantly high. To address this issue, we develop the notion of kernel structure property to obtain necessary and sufficient conditions for the inexistence of spurious local solutions for any class of matrix sensing problems over a given search space. This notion precisely captures the underlying sparsity and structure of the problem, based on tools in conic optimization. We simplify the conditions for a certain class of problems to show their satisfaction and apply them to data analytics for power systems. [ABSTRACT FROM AUTHOR]

The random sampling and reconstruction algorithm of sparse time- and band-limited signals, which stem from bandlimited functions, is studied in this paper. For time- and band-limited signals, considering the projection on a finite-dimensional solution space, the reconstruction algorithm can therefore be described by a matrix. Especially, we study the case of the finite-dimensional spaces with regard to time- and band-limited signals. First, as the cardinality of the sample value { f (x j) : j ∈ J } is not less than the dimension of solution space, we prove that the coefficient matrix has full rank. Second, as sample value { f (x j) : j ∈ J } is insufficient, especially spare time- and band-limited signals, based on the Restricted Isometry Property (RIP) condition and the concentration inequality of a probability distribution for random sampling, we present a ℓ 1 − minimization reconstruction from few randomly chosen samples on [ − T , T ]. Finally, numerical experiments show that with high probability the time- and band-limited signals can be approximately recovered provided τ-sparsity of non-vanishing coefficients ak. [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]

While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k × k principal submatrices—we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objective function value of the original SDP. In this paper, we formally attempt to compare the strength of the sparse SDP relaxation vis-à-vis the original SDP from a theoretical perspective. In order to simplify the question, we arrive at a data independent version of it, where we compare the sizes of SDP cone and the k -PSD closure, which is the cone of matrices where PSD-ness is enforced on all k × k principal submatrices. In particular, we investigate the question of how far a matrix of unit Frobenius norm in the k -PSD closure can be from the SDP cone. We provide two incomparable upper bounds on this farthest distance as a function of k and n. We also provide matching lower bounds, which show that the upper bounds are tight within a constant in different regimes of k and n. Other than linear algebra techniques, we extensively use probabilistic methods to arrive at these bounds. One of the lower bounds is obtained by observing a connection between matrices in the k -PSD closure and matrices satisfying the restricted isometry property. [ABSTRACT FROM AUTHOR]