共查询到20条相似文献,搜索用时 31 毫秒
1.
《Applied and Computational Harmonic Analysis》2014,36(2):316-325
In this paper, we study the performance of the projected Landweber iteration (PLW) for the general low rank matrix recovery. The PLW was first proposed by Zhang and Chen (2010) [43] based on the sparse recovery algorithm APG (Daubechies et al., 2008) [14] in the matrix completion setting, and numerical experiments have been given to show its efficiency (Zhang and Chen, 2010) [43]. In this paper, we focus on providing a convergence rate analysis of the PLW in the general setting of low rank matrix recovery with the affine transform having the matrix restricted isometry property. We show robustness of the algorithm to noise with a strong geometric convergence rate even for noisy measurements provided that the affine transform satisfies a matrix restricted isometry property condition. 相似文献
2.
We analyze a multiple-input multiple-output (MIMO) radar model and provide recovery results for a compressed sensing (CS) approach. In MIMO radar different pulses are emitted by several transmitters and the echoes are recorded at several receiver nodes. Under reasonable assumptions the transformation from emitted pulses to the received echoes can approximately be regarded as linear. For the considered model, and many radar tasks in general, sparsity of targets within the considered angle-range-Doppler domain is a natural assumption. Therefore, it is possible to apply methods from CS in order to reconstruct the parameters of the targets. Assuming Gaussian random pulses the resulting measurement matrix becomes a highly structured random matrix. Our first main result provides an estimate for the well-known restricted isometry property (RIP) ensuring stable and robust recovery. We require more measurements than standard results from CS, like for example those for Gaussian random measurements. Nevertheless, we show that due to the special structure of the considered measurement matrix our RIP result is in fact optimal (up to possibly logarithmic factors). Our further two main results on nonuniform recovery (i.e., for a fixed sparse target scene) reveal how the fine structure of the support set—not only the size—affects the (nonuniform) recovery performance. We show that for certain “balanced” support sets reconstruction with essentially the optimal number of measurements is possible. Indeed, we introduce a parameter measuring the well-behavedness of the support set and resemble standard results from CS for near-optimal parameter choices. We prove recovery results for both perfect recovery of the support set in case of exactly sparse vectors and an \(\ell _2\)-norm approximation result for reconstruction under sparsity defect. Our analysis complements earlier work by Strohmer & Friedlander and deepens the understanding of the considered MIMO radar model. Thereby—and apparently for the first time in CS theory—we prove theoretical results in which the difference between nonuniform and uniform recovery consists of more than just logarithmic factors. 相似文献
3.
We consider the block orthogonal multi-matching pursuit(BOMMP) algorithm for the recovery of block sparse signals.A sharp condition is obtained for the exact reconstruction of block K-sparse signals via the BOMMP algorithm in the noiseless case,based on the block restricted isometry constant(block-RIC).Moreover,we show that the sharp condition combining with an extra condition on the minimum l_2 norm of nonzero blocks of block K-sparse signals is sufficient to ensure the BOMMP algorithm selects at least one true block index at each iteration until all true block indices are selected in the noisy case.The significance of the results we obtain in this paper lies in the fact that making explicit use of block sparsity of block sparse signals can achieve better recovery performance than ignoring the additional structure in the problem as being in the conventional sense. 相似文献
4.
压缩感知(compressed sensing,CS)是一种全新的信息采集与处理理论,它表明稀疏信号能够在远低于Shannon-Nyquist采样率的条件下被精确重构.现从压缩感知理论出发,对块稀疏信号重构算法进行研究,通过混合l2/lq(0
相似文献
5.
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit 总被引:16,自引:0,他引:16
This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear
measurements—L1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of Orthogonal Matching
Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees
of L1-minimization. Our algorithm, ROMP, reconstructs a sparse signal in a number of iterations linear in the sparsity, and the
reconstruction is exact provided the linear measurements satisfy the uniform uncertainty principle.
相似文献
6.
In this paper, we investigate truncated $ℓ_2/ℓ_{1−2}$ minimization and its associated alternating direction method of multipliers (ADMM) algorithm for recovering the block sparse
signals. Based on the block restricted isometry property (Block-RIP), a theoretical analysis is presented to guarantee the validity of proposed method. Our theoretical results
not only show a less error upper bound, but also promote the former recovery condition
of truncated ℓ1−2 method for sparse signal recovery. Besides, the algorithm has been
compared with some state-of-the-art algorithms and numerical experiments have shown
excellent performances on recovering the block sparse signals. 相似文献
7.
《中国科学 数学(英文版)》2017,(10)
In this paper, motivated by the results in compressive phase retrieval, we study the robustness properties of dimensionality reduction with Gaussian random matrices having arbitrarily erased rows. We first study the robustness property against erasure for the almost norm preservation property of Gaussian random matrices by obtaining the optimal estimate of the erasure ratio for a small given norm distortion rate. As a consequence, we establish the robustness property of Johnson-Lindenstrauss lemma and the robustness property of restricted isometry property with corruption for Gaussian random matrices. Secondly, we obtain a sharp estimate for the optimal lower and upper bounds of norm distortion rates of Gaussian random matrices under a given erasure ratio. This allows us to establish the strong restricted isometry property with the almost optimal restricted isometry property(RIP) constants, which plays a central role in the study of phaseless compressed sensing. As a byproduct of our results, we also establish the robustness property of Gaussian random finite frames under erasure. 相似文献
8.
We study the recovery conditions of weighted mixed $\ell_2/\ell_p$ minimization for block sparse signal reconstruction from compressed measurements when partial block support information is available. We show theoretically that the extended block restricted isometry property can ensure robust recovery when the data fidelity constraint is expressed in terms of an $\ell_q$ norm of the residual error, thus establishing a setting wherein we are not restricted to Gaussian measurement noise. We illustrate the results with a series of numerical experiments. 相似文献
9.
V. Churchill & A. Gelb 《计算数学(英文版)》2023,41(2):246-262
This paper presents an application of the sparse Bayesian learning (SBL) algorithm to linear inverse problems with a high order total variation (HOTV) sparsity prior. For the problem of sparse signal recovery, SBL often produces more accurate estimates than maximum a posterioriestimates, including those that use $\ell_1$ regularization. Moreover, rather than a single signal estimate, SBL yields a full posterior density estimate which can be used for uncertainty quantification. However, SBL is only immediately applicable to problems having a directsparsity prior, or to those that can be formed via synthesis. This paper demonstrates how a problem with an HOTV sparsity prior can be formulated via synthesis, and then utilizes SBL. This expands the class of problems available to Bayesian learning to include, e.g., inverse problems dealing with the recovery of piecewise smooth functions or signals from data. Numerical examples are provided to demonstrate how this new technique is effectively employed. 相似文献
10.
Orthogonal matching pursuit(OMP)algorithm is an efcient method for the recovery of a sparse signal in compressed sensing,due to its ease implementation and low complexity.In this paper,the robustness of the OMP algorithm under the restricted isometry property(RIP) is presented.It is shown that δK+√KθK,11is sufcient for the OMP algorithm to recover exactly the support of arbitrary K-sparse signal if its nonzero components are large enough for both l2bounded and l∞bounded noises. 相似文献
11.
Jeffrey D. Blanchard Coralia Cartis Jared Tanner Andrew Thompson 《Applied and Computational Harmonic Analysis》2011,30(2):188-203
A major enterprise in compressed sensing and sparse approximation is the design and analysis of computationally tractable algorithms for recovering sparse, exact or approximate, solutions of underdetermined linear systems of equations. Many such algorithms have now been proven to have optimal-order uniform recovery guarantees using the ubiquitous Restricted Isometry Property (RIP) (Candès and Tao (2005) [11]). However, without specifying a matrix, or class of matrices, it is unclear when the RIP-based sufficient conditions on the algorithm are satisfied. Bounds on RIP constants can be inserted into the algorithms RIP-based conditions, translating the conditions into requirements on the signal's sparsity level, length, and number of measurements. We illustrate this approach for Gaussian matrices on three of the state-of-the-art greedy algorithms: CoSaMP (Needell and Tropp (2009) [29]), Subspace Pursuit (SP) (Dai and Milenkovic (2009) [13]) and Iterative Hard Thresholding (IHT) (Blumensath and Davies (2009) [8]). Designed to allow a direct comparison of existing theory, our framework implies that, according to the best available analysis on these three algorithms, IHT requires the fewest number of compressed sensing measurements, has the best proven stability bounds, and has the lowest per iteration computational cost. 相似文献
12.
《Applied and Computational Harmonic Analysis》2020,48(2):731-765
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. 相似文献
13.
Afonso S. Bandeira Matthew Fickus Dustin G. Mixon Percy Wong 《Journal of Fourier Analysis and Applications》2013,19(6):1123-1149
The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices. 相似文献
14.
Sjoerd Dirksen 《Foundations of Computational Mathematics》2016,16(5):1367-1396
We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson–Lindenstrauss-type results obtained earlier for specific datasets. In particular, we recover and, in several cases, improve results for sets of sparse and structured sparse vectors, low-rank matrices and tensors, and smooth manifolds. In addition, we establish a new Johnson–Lindenstrauss embedding for datasets taking the form of an infinite union of subspaces of a Hilbert space. 相似文献
15.
Tillmann Weisser Jean B. Lasserre Kim-Chuan Toh 《Mathematical Programming Computation》2018,10(1):1-32
We provide a sparse version of the bounded degree SOS hierarchy BSOS (Lasserre et al. in EURO J Comp Optim:87–117, 2017) for polynomial optimization problems. It permits to treat large scale problems which satisfy a structured sparsity pattern. When the sparsity pattern satisfies the running intersection property this Sparse-BSOS hierarchy of semidefinite programs (with semidefinite constraints of fixed size) converges to the global optimum of the original problem. Moreover, for the class of SOS-convex problems, finite convergence takes place at the first step of the hierarchy, just as in the dense version. 相似文献
16.
Structure-enforced matrix factorization (SeMF) represents a large class of mathematical models appearing in various forms of principal component analysis, sparse coding, dictionary learning and other machine learning techniques useful in many applications including neuroscience and signal processing. In this paper, we present a unified algorithm framework, based on the classic alternating direction method of multipliers (ADMM), for solving a wide range of SeMF problems whose constraint sets permit low-complexity projections. We propose a strategy to adaptively adjust the penalty parameters which is the key to achieving good performance for ADMM. We conduct extensive numerical experiments to compare the proposed algorithm with a number of state-of-the-art special-purpose algorithms on test problems including dictionary learning for sparse representation and sparse nonnegative matrix factorization. Results show that our unified SeMF algorithm can solve different types of factorization problems as reliably and as efficiently as special-purpose algorithms. In particular, our SeMF algorithm provides the ability to explicitly enforce various combinatorial sparsity patterns that, to our knowledge, has not been considered in existing approaches. 相似文献
17.
Claire Boyer Jérémie Bigot Pierre Weiss 《Applied and Computational Harmonic Analysis》2019,46(2):312-350
Compressed Sensing (CS) is an appealing framework for applications such as Magnetic Resonance Imaging (MRI). However, up-to-date, the sensing schemes suggested by CS theories are made of random isolated measurements, which are usually incompatible with the physics of acquisition. To reflect the physical constraints of the imaging device, we introduce the notion of blocks of measurements: the sensing scheme is not a set of isolated measurements anymore, but a set of groups of measurements which may represent any arbitrary shape (parallel or radial lines for instance). Structured acquisition with blocks of measurements are easy to implement, and provide good reconstruction results in practice. However, very few results exist on the theoretical guarantees of CS reconstructions in this setting. In this paper, we derive new CS results for structured acquisitions and signals satisfying a prior structured sparsity. The obtained results provide a recovery probability of sparse vectors that explicitly depends on their support. Our results are thus support-dependent and offer the possibility for flexible assumptions on the sparsity structure. Moreover, the results are drawing-dependent, since we highlight an explicit dependency between the probability of reconstructing a sparse vector and the way of choosing the blocks of measurements. Numerical simulations show that the proposed theory is faithful to experimental observations. 相似文献
18.
本文通过引入支撑集捕获基数及MP广义逆,提出了一种用于稀疏恢复问题的矩阵广义逆硬阈值追踪算法,并在观测误差存在的情况下给出了算法在约束等距条件(RIP)下的收敛性.数值实验表明,算法不仅极大地减少了收敛所需迭代次数,且观测误差存在的情况下稀疏恢复是强健的. 相似文献
19.
EQUIVALENCE BETWEEN NONNEGATIVE SOLUTIONS TO PARTIAL SPARSE AND WEIGHTED l1-NORM MINIMIZATIONS
下载免费PDF全文
![点击此处可从《应用数学年刊》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Based on the range space property (RSP), the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted l1-norm minimization problem are studied in this paper. Different from other conditions based on the spark property, the mutual coherence, the null space property (NSP) and the restricted isometry property (RIP), the RSP-based conditions are easier to be verified. Moreover, the proposed conditions guarantee not only the strong equivalence, but also the equivalence between the two problems. First, according to the foundation of the strict complementarity theorem of linear programming, a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix, is presented for the unique nonnegative solution to the weighted l1-norm minimization problem. Then, based on this condition, the equivalence conditions between the two problems are proposed. Finally, this paper shows that the matrix with the RSP of order k can guarantee the strong equivalence of the two problems. 相似文献