首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 93 毫秒
1.
In this paper we investigate the efficiency of the Orthogonal Matching Pursuit algorithm (OMP) for random dictionaries. We concentrate on dictionaries satisfying the Restricted Isometry Property. We also introduce a stronger Homogenous Restricted Isometry Property which we show is satisfied with overwhelming probability for random dictionaries used in compressed sensing. For these dictionaries we obtain upper estimates for the error of approximation by OMP in terms of the error of the best n-term approximation (Lebesgue-type inequalities). We also present and discuss some open problems about OMP. This is a development of recent results obtained by D.L. Donoho, M. Elad and V.N. Temlyakov.  相似文献   

2.
The Johnson–Lindenstrauss lemma asserts that an n‐point set in any Euclidean space can be mapped to a Euclidean space of dimension k = O‐2 log n) so that all distances are preserved up to a multiplicative factor between 1 ? ε and 1 + ε. Known proofs obtain such a mapping as a linear map R n → R k with a suitable random matrix. We give a simple and self‐contained proof of a version of the Johnson–Lindenstrauss lemma that subsumes a basic versions by Indyk and Motwani and a version more suitable for efficient computations due to Achlioptas. (Another proof of this result, slightly different but in a similar spirit, was given independently by Indyk and Naor.) An even more general result was established by Klartag and Mendelson using considerably heavier machinery. Recently, Ailon and Chazelle showed, roughly speaking, that a good mapping can also be obtained by composing a suitable Fourier transform with a linear mapping that has a sparse random matrix M; a mapping of this form can be evaluated very fast. In their result, the nonzero entries of M are normally distributed. We show that the nonzero entries can be chosen as random ± 1, which further speeds up the computation. We also discuss the case of embeddings into R k with the ?1 norm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008  相似文献   

3.
We show that a certain construction of a Lindenstrauss space based on intersections of balls, which was done first by Lindenstrauss and Wulbert, leads to a Gurarij space (of any density character). This provides us with new simple proofs of some assertions about Gurarij spaces as well as of the following:Any compact Choquet simplex (not necessarily metrizable) is affinely homomorphic to a face of a Poulsen simplex S, i.e., a compact Choquet simplex whose extreme points are dense in all S.  相似文献   

4.
In this article, we investigate the privacy issues that arise from a new frame-based kernel analysis approach to reconstruct from frame coefficient erasures. We show that while an erasure recovery matrix is needed in addition to a decoding frame for a receiver to recover the erasures, the erasure recovery matrix can be designed in such a way that it protects the encoding frame. The set of such erasure recovery matrices is shown to be an open and dense subset of a certain matrix space. We present algorithms to construct concrete examples of encoding frame and erasure recovery matrix pairs for which the erasure reconstruction process is robust to additive channel noise. Using the Restricted Isometry Property, we also provide quantitative bounds on the amplification of sparse additive channel noise. Numerical experiments are presented on the amplification of additive normally distributed random channel noise. In both cases, the amplification factors are demonstrated to be quite small.  相似文献   

5.
We discuss necessary and sufficient conditions for a sensing matrix to be “s-good”—to allow for exact 1-recovery of sparse signals with s nonzero entries when no measurement noise is present. Then we express the error bounds for imperfect 1-recovery (nonzero measurement noise, nearly s-sparse signal, near-optimal solution of the optimization problem yielding the 1-recovery) in terms of the characteristics underlying these conditions. Further, we demonstrate (and this is the principal result of the paper) that these characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact sparse 1-recovery and to efficiently computable upper bounds on those s for which a given sensing matrix is s-good. We establish also instructive links between our approach and the basic concepts of the Compressed Sensing theory, like Restricted Isometry or Restricted Eigenvalue properties.  相似文献   

6.
Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x 1,…,x n X, there exists a linear mapping L:XF, where FX is a linear subspace of dimension O(log n), such that ‖x i x j ‖≤‖L(x i )−L(x j )‖≤O(1)⋅‖x i x j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 22O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E n Y whose Euclidean distortion is at least 2Ω(α(n)), where α is the inverse Ackermann function.  相似文献   

7.
We establish a stochastic nonlinear analogue of the Perron–Frobenius theorem on eigenvalues and eigenvectors of positive matrices. The result is formulated in terms of an automorphism T of a probability space and a random transformation D of the non-negative cone of an n-dimensional Euclidean space. Under assumptions of monotonicity and homogeneity of D, we prove the existence of scalar and vector measurable functions α > 0 and x > 0 satisfying the equation αTx = D(x) almost surely. We apply the result obtained to the analysis of a class of random dynamical systems arising in mathematical economics and finance (von Neumann–Gale dynamical systems).  相似文献   

8.
In this paper, we present simple proofs for the main results that appear in Nunez (Math Program 91:375–390, 2002) using a lemma in Freund and Vera (Math Program 86:225–260, 1999) for conic linear programming. Connections between interiors and boundaries of feasible and infeasible data instances and weak and strong feasibilities of a conic linear programming primal-dual pair are made.  相似文献   

9.
The Fast Johnson–Lindenstrauss Transform (FJLT) was recently discovered by Ailon and Chazelle as a novel technique for performing fast dimension reduction with small distortion from 2 d to 2 k in time O(max {dlog d,k 3}). For k in [Ω(log d),O(d 1/2)], this beats time O(dk) achieved by naive multiplication by random dense matrices, an approach followed by several authors as a variant of the seminal result by Johnson and Lindenstrauss (JL) from the mid 1980s. In this work we show how to significantly improve the running time to O(dlog k) for k=O(d 1/2−δ ), for any arbitrary small fixed δ. This beats the better of FJLT and JL. Our analysis uses a powerful measure concentration bound due to Talagrand applied to Rademacher series in Banach spaces (sums of vectors in Banach spaces with random signs). The set of vectors used is a real embedding of dual BCH code vectors over GF(2). We also discuss the number of random bits used and reduction to 1 space. The connection between geometry and discrete coding theory discussed here is interesting in its own right and may be useful in other algorithmic applications as well.  相似文献   

10.
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.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号