A Simple Proof of the Restricted Isometry Property for Random Matrices

We give a simple technique for verifying the Restricted Isometry Property (as introduced by Candès and Tao) for random matrices that underlies Compressed Sensing. Our approach has two main ingredients: (i) concentration inequalities for random inner products that have recently provided algorithmically simple proofs of the Johnson–Lindenstrauss lemma; and (ii) covering numbers for finite-dimensional balls in Euclidean space. This leads to an elementary proof of the Restricted Isometry Property and brings out connections between Compressed Sensing and the Johnson–Lindenstrauss lemma. As a result, we obtain simple and direct proofs of Kashin’s theorems on widths of finite balls in Euclidean space (and their improvements due to Gluskin) and proofs of the existence of optimal Compressed Sensing measurement matrices. In the process, we also prove that these measurements have a certain universality with respect to the sparsity-inducing basis.      

The Performance of Orthogonal Multi-Matching Pursuit under the Restricted Isometry Property

The orthogonal multi-matching pursuit (OMMP) is a natural extension of the orthogonal matching pursuit (OMP).We denote the OMMP with the parameter $M$ as OMMP($M$) where $M$ ≥ 1 is an integer. The main difference between OMP and OMMP($M$) is that OMMP($M$) selects $M$ atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit under RIP. In particular, we show that, when the measurement matrix $A$ satisfies (25$s$, 1/10)-RIP, OMMP($M_0$) with $M_0$ = 12 can recover $s$-sparse signals within $s$ iterations. We furthermore prove that OMMP($M$) can recover $s$-sparse signals within $O(s/M)$ iterations for a large class of $M$.     

Suprema of Chaos Processes and the Restricted Isometry Property

We present a new bound for suprema of a special type of chaos process indexed by a set of matrices, which is based on a chaining method. As applications we show significantly improved estimates for the restricted isometry constants of partial random circulant matrices and time‐frequency structured random matrices. In both cases the required condition on the number m of rows in terms of the sparsity s and the vector length n is m ? s log² s log² n. © 2014 Wiley Periodicals, Inc.     

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

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

The Isometry of Riemannian Manifold to a Sphere

ＴｈｅＩｓｏｍｅｔｒｙｏｆＲｉｅｍａｎｎｉａｎＭａｎｉｆｏｌｄｔｏａＳｐｈｅｒｅＺｈａｏＰｅｉｂｉａｏ（赵培标）（Ｄｅｐｔ．ｏｆＭａｔｈ．，ＡｎｈｕｉＩｎｓｔｉｔｕｔｅｏｆＦｉｎａｎｃｅ＆Ｔｒａｄｅ，２３３０４１）Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐ...     

Restricted Mean Value Property for Balayage Spaces with Jumps

It is shown that, for α-stable processes (Riesz potentials) or—more generally—for balayage spaces with jumps, “one-radius” results for harmonicity can be obtained under fairly weak assumptions.     

广义循环矩阵的一个性质

可表为非奇异对角矩阵和循环矩阵乘积的矩阵,我们称其为广义循环矩阵.本文给出了单位矩阵与广义循环矩阵的和矩阵的非奇异的充要条件,得到了这样和矩阵的相对增益阵列的显示表达式.     

上三角算子矩阵的单值延拓性质的摄动

设H为无限维可分的复Hilbert空间,B(H)为H上的有界线性算子全体.算子T∈B(H)称为具有单值延拓性质,若对任意一个开集U(?)C,满足方程(T-λI)f(λ)=0(任给λ∈U)的唯一的解析函数f:U→H为零函数;T∈B(H)称为满足单值延拓性质的稳定性,若对任意一个紧算子K∈B(H),T+K都满足单值延拓性质.本文给出了2×2上三角算子矩阵在紧摄动下满足单值延拓性质的稳定性的特征.     

Restricted Interpolation and the Projective Beth Property in Equational Logic

Interconnections between syntactic and categorical properties of equational theories are established. The notions of restricted interpolation and of restricted amalgamation are introduced and their equivalence proved; interrelations of the above-mentioned properties and the projective Beth property, interpolation, and amalgamation are studied.     

The Serial Property and Restricted Balanced Contributions in discrete cost sharing problems

We show that the Serial Poperty and Restricted Balanced Contributions characterize the subsidy-free serial cost sharing method (Moulin (1995)) in discrete cost allocation problems. This research has been partially supported by the Universidad del País Vasco (project UPV 00031.321-15352/2003), MCyT under projects BEC2003-08182 and SEJ2004-07554, and by the Generalitat Valenciana under project GRUPOS04/13.     

The Generalized Pompeiu Metric in the Isometry Problem for Hyperspaces

The isometries of the hyperspace of a compact subset of the real line endowed with the generalized Pompeiu metric are considered. It is proved that any such an isometry is generated by an isometry of the base space.__________Translated from Matematicheskie Zametki, vol. 78, no. 2, 2005, pp. 163–170.Original Russian Text Copyright © 2005 by V. V. Aseev, A. V. Tetenov, A. P. Maksimova.     

利用矩阵的初等变换求方阵的特征值

高阶方阵的特征值的求得,需求解一元高次方程,这往往有一定的难度.本文依据矩阵的初等变换的一些良好性质,介绍两种利用矩阵的初等变换化简方阵的特征值的计算的方法.     

Matrices with permanent equal to one

We show that a nonnegative square matrix M is nilpotent if and only if the permanent of M + I is one. We also show that a 2-complex obtained by sewing disks to a wedge of circles is collapsible if and only if its incidence matrix has permanent one.     

Deterministic representation of chaos with application to turbulence

Chaos and unpredictability in some classical dynamic systems are eliminated by referring the governing equation to a specially selected rapidly oscillating (non-inertial) frame of reference in which the stabilization effect is caused by inertia forces. The resulting motion is found as a sum of smooth and non-smooth (rapidly oscillating) parts. The solution is stable and reproducible in the sense that small changes in initial conditions lead to small changes in both smooth and non-smooth components. In this interpretation, conceptually the closure problem in turbulence is reduced to the problem of finding such a frame of reference where the high Reynolds number instability is eliminated. The usefulness of the approach is illustrated by examples.     

限制性卖空的均值-方差投资组合优化

本文提出了限制性卖空的均值-方差投资组合模型,通过变量替换将该模型转变为一般二次规划问题,从而运用不等式组的旋转算法进行求解.文章还以一个具体例子验证该算法的有效性,并证明在一定变化范围内,借入资产的资金与总资金的比例越大越有助于拓展投资机会空间.     

Pascal算子矩阵在组合恒等式中的应用

定义了四种Pascal算子矩阵,给出了它们的代数性质及它们之间的关系,并且利用二项式型多项式序列、算子及哑运算得到许多组合恒等式.     

反对角算子矩阵及其平方的(ω)性质的摄动

设H为复的无限维可分的Hilbert空间,B(H)为H上的有界线性算子的全体.若σ_a(T)\σ_(ea)(T)=π_(00)(T),则称T∈B(H)满足(ω)性质,其中σ_a(T)和σ_(ea)(T)分别表示算子T的逼近点谱和本质逼近点谱,π_(00)(T)={λ∈isoσ(T):0dimN(T-λI)∞}.T∈B(H)称为满足(ω)性质的摄动,若对任意的紧算子K,T+K满足(ω)性质.本文证明了反对角算子矩阵及其平方具有(ω)性质的摄动的等价性.     

Pascal算子矩阵在组合恒等式中的应用(英文)

定义了四种Pascal算子矩阵,给出了它们的代数性质及它们之间的关系,并且利用二项式型多项式序列、算子及哑运算得到许多组合恒等式.     

The Bumpy Road to the Mode Forest

Abstract

The mode tree of Minnotte and Scott provides a valuable method of investigating features such as modes and bumps in a unknown density. By examining kernel density estimates for a range of bandwidths, we can learn a lot about the structure of a data set. Unfortunately, the basic mode tree can be strongly affected by small changes in the data, and gives no way to differentiate between important modes and those caused, for example, by outliers. The mode forest overcomes these difficulties by looking simultaneously at a large collection of mode trees, all based on some variation of the original data, by means such as resampling or jittering. The resulting graphic tool is both visually appealing and informative.     

增长型经济变量的趋势时间序列预测模型

针对增长型外汇储备时间序列变化复杂性的特点,可以建立确定性趋势的时间序列模型及包含单位根的随机趋势模型.实际计算显示,确定性趋势的时间序列模型具有较高的预测精度.