Robustness of orthogonal matching pursuit under restricted isometry property

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.     

Weighted $\ell_p$-Minimization for Sparse Signal Recovery under Arbitrary Support Prior

Weighted $\ell_p$ ($0相似文献   

弱化限制等距性的稀疏信号恢复

众所周知,传统的信号压缩和重建遵循香农一耐奎斯特采样定律,即采样率必须至少为信号最高频率的两倍,才能保证在重建时不产生失真,这无疑将给信号采样,传输和存储过程带来越来越大的压力.随着科技的飞速发展,特别是近年来传感器技术获取数据能力提高,物联网等促使人类社会的数据规模遽增,大数据时代正式到来.大数据的规模效应给数据存储,传输,管理以及数据分析带来了极大的挑战.压缩采样应运而生.限制等距性(Restricted Isometry Property,RIP)在压缩传感中起着关键的作用.只有满足限制等距条件的压缩矩阵才能平稳恢复原始信号.RIP作为衡量矩阵是否能作为测量矩阵得到了认可,但是此理论的缺陷在于对任一矩阵,很难有通用,快速的算法来验证其是否满足RIP条件.很多学者尝试弱化RIP条件以找到测量矩阵构造的突破口.首先构造了新的限制等距条件δ_(1.5k)+θ_(k,1.5k)≤1,然后证明在这个条件下无噪声稀疏信号能被精确的恢复,并且噪声稀疏信号能被平稳的估计.最后,通过比较表明δ_(1.5k)+θ_(k,1.5k)≤1优于现存的条件.     

CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix–vector multiplies with the sampling matrix. For compressible signals, the running time is just O(Nlog²N), where N is the length of the signal.     

半定矩阵秩极小的非凸精确松弛

本文主要研究半定矩阵秩极小问题(P)的非凸精确松弛及其性质.首先,为求解问题(P),我们引入其Schatten p-范数(0＜p＜1)松弛,记为(Sp).其次,通过定义半定限制等距常数和半定限制正交常数,我们给出了问题(P)有唯—解的充分条件.最后,利用半定限制等距性质,我们给出了问题(P)和(Sp)有相同唯一解的充分条件.特别地,对任意0＜p＜1,我们还得到—个一致的精确恢复条件.     

Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit

This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements—L₁-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 L₁-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.      

Fiducial intervals of restricted parameters and their applications

In practice, the unknown parameters are often restricted. This paper provides a general method for constructing the fiducial intervals of the restricted parameters. Applying the general method, the fiducial intervals are constructed for the location (scale) parameters and the difference (ratio) of two locations (scales) in a location (scale) family of distributions. The frequency properties of these intervals are verified. For a variance components model, the fiducial intervals for the three parameters of common interest are obtained. Their frequency properties are investigated theoretically and computationally.     

Influences of preconditioning on the mutual coherence and the restricted isometry property of Gaussian/Bernoulli measurement matrices

This article discusses the influence of preconditioning on the mutual coherence and the restricted isometry property of Gaussian or Bernoulli measurement matrices. The mutual coherence can be reduced by preconditioning, although it is fairly small due to the probability estimate of the event that it is less than any given number in (0, 1). This can be extended to a set that contains either of the two types of matrices with a high probability but a subset with Lebesgue measure zero. The numerical results illustrate the reduction in the mutual coherence of Gaussian or Bernoulli measurement matrices. However, the first property can be true after preconditioning for a large type of measurement matrices having the property of s-order restricted isometry and being full row rank. This leads to a better estimate of the condition number of the corresponding submatrices and a more accurate error estimate of the conjugate gradient methods for the least squares problems typically used in greedy-like recovery algorithms.     

Uniform recovery from subgaussian multi-sensor measurements

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.     

On the equivalence of the BLUEs under a general linear model and its restricted and stochastically restricted models

Necessary and sufficient conditions are derived for the equalities of the best linear unbiased estimators (BLUEs) of parametric functions under a general linear model and its restricted and stochastically restricted models to hold.     

Convergence of projected Landweber iteration for matrix rank minimization

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.     

Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method

In this paper, we propose a Quasi-Orthogonal Matching Pursuit (QOMP) algorithm for constructing a sparse approximation of functions in terms of expansion by orthonormal polynomials. For the two kinds of sampled data, data with noises and without noises, we apply the mutual coherence of measurement matrix to establish the convergence of the QOMP algorithm which can reconstruct $s$-sparse Legendre polynomials, Chebyshev polynomials and trigonometric polynomials in $s$ step iterations. The results are also extended to general bounded orthogonal system including tensor product of these three univariate orthogonal polynomials. Finally, numerical experiments will be presented to verify the effectiveness of the QOMP method.     

Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares

In countless applications, we need to reconstruct a $K$-sparse signal $\mathbf{x}\in\mathbb{R}^n$ from noisy measurements $\mathbf{y}=\mathbf{\Phi}\mathbf{x}+\mathbf{v}$, where $\mathbf{\Phi}\in\mathbb{R}^{m\times n}$ is a sensing matrix and $\mathbf{v}\in\mathbb{R}^m$ is a noise vector. Orthogonal least squares (OLS), which selects at each step the column that results in the most significant decrease in the residual power, is one of the most popular sparse recovery algorithms. In this paper, we investigate the number of iterations required for recovering $\mathbf{x}$ with the OLS algorithm. We show that OLS provides a stable reconstruction of all $K$-sparse signals $\mathbf{x}$ in $\lceil2.8K\rceil$ iterations provided that $\mathbf{\Phi}$ satisfies the restricted isometry property (RIP). Our result provides a better recovery bound and fewer number of required iterations than those proposed by Foucart in 2013.     

Recovery of signals under the condition on RIC and ROC via prior support information

In this paper, the sufficient condition in terms of the RIC and ROC for the stable and robust recovery of signals in both noiseless and noisy settings was established via weighted $l_1$ minimization when there is partial prior information on support of signals. An improved performance guarantee has been derived. We can obtain a less restricted sufficient condition for signal reconstruction and a tighter recovery error bound under some conditions via weighted $l_1$ minimization. When prior support estimate is at least 50% accurate, the sufficient condition is weaker than the analogous condition by standard $l_1$ minimization method, meanwhile the reconstruction error upper bound is provably to be smaller under additional conditions. Furthermore, the sufficient condition is also proved sharp.     

桉树扦插育苗正交试验设计分析

根据扦插育苗试验表明，影响泰国赤桉苗高、根长及发根数的主要因素各不相同。综合分析表明：其主要因素是ＢＡ浓度，插条浸泡药液的时间和蔗糖浓度，其较优的插条处理方法是将插条在０．６％蔗糖＋３００ＰＰｍＩＢＡ溶液中浸泡２小时     

On the convergence of higher-order orthogonal iteration

The higher-order orthogonal iteration (HOOI) has been popularly used for finding a best low-multilinear rank approximation of a tensor. However, its convergence is still an open question. In this paper, we first analyse a greedy HOOI, which updates each factor matrix by selecting from the best candidates one that is closest to the current iterate. Assuming the existence of a block-nondegenerate cluster point, we establish its global iterate sequence convergence through the so-called Kurdyka–?ojasiewicz property. In addition, we show that if the starting point is sufficiently close to any block-nondegenerate globally optimal solution, the greedy HOOI produces an iterate sequence convergent to a globally optimal solution. Relating the iterate sequence by the original HOOI to that by the greedy HOOI, we then show that the original HOOI has global convergence on the multilinear subspace sequence and thus positively address the open question.     

Subspaces,angles and pairs of orthogonal projections

We give a new proof for the Wedin theorem on the simultaneous unitary similarity transformation of two orthogonal projections and show that it is equivalent to Halmos' theorem on the unitary equivalence of projection pairs. As a consequence of these theorems, we derive several results on pairs of orthogonal projections, relative subspace positions and oblique projections as well.     

Risk-minimizing hedging strategies under restricted information: The case of stochastic volatility models observable only at discrete random times

We consider a market where the price of the risky asset follows a stochastic volatility model, but can be observed only at discrete random time points. We determine a local risk minimizing hedging strategy, assuming that the information of the agent is restricted to the observations of the price at its random jump times. Stochastic filtering also comes into play when computing the hedging strategy in the given situation of restricted information.     

Synchronization of nonlinear master–slave systems under input delay and slope‐restricted input nonlinearity

This article addresses the synchronization of nonlinear master–slave systems under input time‐delay and slope‐restricted input nonlinearity. The input nonlinearity is transformed into linear time‐varying parameters belonging to a known range. Using the linear parameter varying (LPV) approach, applying the information of delay range, using the triple‐integral‐based Lyapunov–Krasovskii functional and utilizing the bounds on nonlinear dynamics of the nonlinear systems, nonlinear matrix inequalities for designing a simple delay‐range‐dependent state feedback control for synchronization of the drive and response systems is derived. The proposed controller synthesis condition is transformed into an equivalent but relatively simple criterion that can be solved through a recursive linear matrix inequality based approach by application of cone complementary linearization algorithm. In contrast to the conventional adaptive approaches, the proposed approach is simple in design and implementation and is capable to synchronize nonlinear oscillators under input delays in addition to the slope‐restricted nonlinearity. Further, time‐delays are treated using an advanced delay‐range‐dependent approach, which is adequate to synchronize nonlinear systems with either higher or lower delays. Furthermore, the resultant approach is applicable to the input nonlinearity, without using any adaptation law, owing to the utilization of LPV approach. A numerical example is worked out, demonstrating effectiveness of the proposed methodology in synchronization of two chaotic gyro systems. © 2015 Wiley Periodicals, Inc. Complexity 21: 220–233, 2016     

Analysis of μM,D‐orthogonal exponentials for the planar four‐element digit sets

The self‐affine measure is a unique probability measure satisfying the self‐affine identity with equal weight. It only depends upon an expanding matrix M and a finite digit set D. In this paper we study the question of when the ‐space has infinite families of orthogonal exponentials. Such research is necessary to further understanding the spectrality of . For a class of planar four‐element digit sets, we present several methods to deal with this question. The application of each method is also given, which extends the known results in a simple manner.