近日， 在导师武汉大学邹秀芬教授的悉心指导下， 自已最新的一篇论文被数学权威期刊 Applied Mathematical Modelling 杂志接受并Online, 有点小激动，这是7月份接受的第二篇关于多层网络关键节点识别的论文，希望大家喜欢。在这篇论文中，我们考虑多层网络的四个中心性指标：Authority and hub centralities of nodes, Authority and hub centralities of layers。基于多层网络的4阶张量表示和单层网络HITS中心性算法的迭代思想，我设计一个新颖的基于张量计算的迭代格式去获得上面四个中心性指标，并且我们从理论上证明了这个迭代格式的收敛性。最后通过整合这四个指标，我们提出了一个新颖的中心性指标Singular Vector of Tensors (SVT) centrality去识别多层网络的关键节点。数值实验证明我们的算法具有较好的性能。 Title: A new centrality measure of nodes in multilayer networks under the framework of tensor computation Online Web Page: http://www.sciencedirect.com/science/article/pii/S0307904X1730450X Abstract: One challenging issue in information science, biological systems and many other field is to determine the most central agents in multilayer networked systems characterized by different types of interrelationships. In this paper, using a fourth-order tensor to represent multilayer networks, we propose a new centrality measure, referred to as the Singular Vector of Tensor (SVT) centrality, which is used to quantitatively evaluate the importance of nodes connected by different types of links in multilayer networks. First, we present a novel iterative method to obtain four alternative metrics that can quantify the hub and authority scores of nodes and layers in multilayer networked systems. Moreover, we use the theory of multilinear algebra to prove that the four metrics converge to four singular vectors of the adjacency tensor of the multilayer network under reasonable conditions. Furthermore, a novel SVT centrality measure is obtained by integrating these four metrics. The experimental results demonstrate that the proposed method is a new centrality measure that significantly outperforms six other published centrality methods on two real-world multilayer networks related to complex diseases, i.e., gastric and colon cancers. Keywords: Multilayer networks, tensor representation, centrality, essential nodes, tensor iterative computation, singular vector of tensor (SV T)
此文又是Bengio大神的综述，2013年，内容更新，与09年那篇综述侧重点稍有不同，同样，需要完全读懂需要很好的基础和时间，反正我是很多地方懵懵懂懂，姑且将自己的翻译和摘取贴出来大家互相交流，如有不对的地方欢迎指正。 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1. Introduction 2. Why should we care about learning representation? Although depth is an important part of the story, many other priors are interesting and can be conveniently captured by a learner when the learning problem is cast as one of learning a representation. 接下来几个领域的应用： Speech Recognition and Signal Processing Object Recognition MNIST最近的记录：Ciresan et al. (2012) 0.27% Rifai et al. (2011c) 0.81% ImageNet：Krizhevsky et al.(2012) 15.3% Natural Language Processing Multi-Task and Transfer Learning, Domain Adaptation 3. What makes a representation good? 3.1 Priors for representation learning in AI a. Smoothness b. Multiple explanatory factors: 数据形成的分布是由一些隐含factors生成的 c. A hierarchical organization of explanatory factors：变量的层次结构 d. Semi-supervised learning e. Shared factors across tasks f. Manifolds:流形学习，主要用于AE的研究 g. Natural clustering h. Temporal and spatial coherence i. Sparsity 这些priors都可以用来帮助learner学习representation。 3.2 Smoothness and the Curse of Dimensionality 机器学习局部非参数学习例如核函数，它们只能获取局部泛化，假设目标函数是足够平滑的，但这不足以解决维度灾难。这些叫smoothness based learner和线性模型仍然可以用在这些学习到的表示的顶层。实际上，学习一个表示和核函数等同于学习一个核。 3.3 Distributed representations 一个one-hot表示，例如传统的聚类算法、高斯混合模型。最近邻算法、高斯SVM等的结果都需要O(N)个参数来区分O(N)个输入区域。但是像 RBM、sparse coding、auto-encoder或者多层神经网络可以用O(N)个参数表示 个输入区域。它们就是分布式表示。 3.4 Depth and abstraction 深度带来了两个明显的提高：促进特征的重复利用、潜在的获取更抽象的高层特征。 re-use： 深度回路的一个重要性质是path的数量，它会相对于深度呈指数级增长。我们可以改变每个节点的定义来改变回路的深度。典型的计算包括：weighted,sum, product, artificial neuron model,computation of a kernel, or logic gates. Abstraction and invariance 更抽象的概念可以依靠less抽象的概念构造。例如在CNN中，通过pooling来构造这种抽象，更抽象的概念一般是对于大部分输入的局部变化具有不变性。 3.5 Disentangle factors of variation 最鲁棒的特征学习是尽可能多的解决factors，抛弃尽可能少的信息，类似降维。 3.6 What are good criteria for learning representations? 在分类中，目标很明显就是最小化错误分类，但是表示学习不一样，这是一个值得思考的问题。 4. Building deep representations 06年在特征学习方面有一个突破，中心思想就是贪婪单层非监督预训练，学习层次化的特征，每次一层，用非监督学习来学习组合之前学习的transformation。 单层训练模式也可以用于监督训练，虽然效果不如非监督训练，但比没有预训练要好。 下面几种方法组合单层网络来构成监督模型： 层叠RBM形成DBN ，但是怎么去估计最大似然来优化生产模型目前还不是很清楚，一种选择是wake-sleep算法。 另一种方法是 结合RBM参数到DBM 中，基本上就是减半。 还有一种方法是 层叠RBM或者AE形成深层自编码器 ， 另一种方法训练深层结构是iterative construction of a free energy function 5. Single-layer learning modules 在特征学习方面，有两条主线：一个根源于PGM，一个根源于NN。 根本上这两个的区别在于每一层是描述为PGM还是computational graph，简单的说，就是隐层节点便是latent random variables还是computational nodes。 RBM是在PGM这一边，AE在NN这一边。在RBM中，用score matching训练模型本质上与AE的规则化重建目标是想通的。 PCA三种解释： a. 与PM相关，例如probabilistic PCA、factor analysis和传统的多元变量高斯分布。 b. 它本质上和线性AE相同 c. 它可以看成是线性流形学习的一种形式 但是线性特征的表达能力有限，他不能层叠老获取更抽象的表示，因为组合线性操作最后还是产生线性操作。 6. Probabilistic Models Learning is conceived in term of estimating a set of model parameters that (locally) maximizes the likelihood of the training data with respect to the distribution over these latent variables. 6.1 Directed Graphical Models 6.1.1 Explaining away 一个事件先验独立的因素在给出了观察后变得不独立了，这样即使h是离散的，后验概率P(h|x)也变的intractable。 6.1.2 Probabilistic interpretation of PCA 6.1.3 Sparse coding 稀疏编码和PCA的区别在于包含一个惩罚来保证稀疏性。 Laplace分布（等同于L1惩罚）产生稀疏表示。与RBM和AE比较，稀疏编码中的推理包含了一个内在循环的优化也就增加了计算复杂度，稀疏编码中的编码对每一个样本是一个free variable，在那种意义上潜在的编码器是非参数的。 6.2 Undirected Graphical Models 无向图模型，也叫马尔科夫随机场（MRF），一种特殊形式叫BM，其能力方程： 6.2.1 RBM 6.3 Generalization of the RBM to real-valued data 最简单的方法是Gaussian RBM，但是 Ranzato2010 给出了更好的方法来model自然图像，叫做 mean and covariance RBM（mcRBM） ，这是covariance RBM和GRBM的结合。还介绍了mPoT模型。 Courville2011 提出了ssRBM在CIFAR-10上取得了很好的表现。 这三个模型都用来model real-valued data，隐层单元不仅编码了数据的conditional mean，还是conditional covariance。不同于训练方法，这几个的区别在于怎么encode conditional covariance。 6.4 RBM parameter estimation 6.4.1 Contrastive Divergence 6.4.2 Stochastic Maximum Likelihood（SML/PCD） 在每一步梯度更新时，不像CD算法中positive phase中gibbs sampling每次都更新，而是用前一次更新过的状态。但是当权值变大，估计的分布就有更多的峰值，gibbs chain就需要很长的时间mix。 Tieleman2009 提出一种fast-weight PCD（FPCD）算法用来解决这个问题。 6.4.3 Pseudolikelihood，Ratio-matching and other Inductive Principles Marlin2010 比较了CD和SML。 7. Direct Encoding: Learning a Parametric Map from Input to Representation 7.1 Auto-Encoders 特征提取函数和重构误差函数根据应用领域不同而不同。 对于无界的输入，用线性解码器和平方重构误差。对于 之间的输入，使用sigmoid函数。如果是二值输入，可以用binary cross-entropy误差。 binary cross-entropy： 线性编码和解码得到类似于PCA的subspace，当使用sigmoid非线性编码器的时候也一样，但是权值如果是tied就不同了。 如果编码器和解码器都使用sigmoid非线性函数，那么他得到类似binary RBM的特征。一个不同点在于RBM用一个单一的矩阵而AE在编码和解码使用不同的权值矩阵。 在实际中AE的优势在于它定义了一个简单的tractable优化目标函数，可以用来监视进程。 7.2 Regularized Auto-encoders 传统的AE就像PCA一样，作为一种数据降维的方法，因此用的是 bottleneck 。而 RBM和sparse coding倾向于over-complete表示 ，这可能导致AE太简单（直接复制输入到特征）。这就需要regularization，可以把它看成让表示对输入的变化不太敏感。 7.2.1 Sparse Auto-encoders 当直接惩罚隐层单元时，有很多变体，但没有文章比较他们哪一个更好 。虽然L1 penalty看上去最自然，但很少SAE的文章用到。一个类似的规则是student-t penalty 。详见UFLDL。 7.2.2 Denoising Auto-encoders Vincent2010 中考虑了对灰度图加入等向高斯噪声、椒盐噪声。 7.2.3 Contractive Auto-encoders Refai2011 提出了CAE与DAE动机一样，也是要学习鲁棒的特征，通过加入一个analytic contractive penalty term。 令Jacobian matrix ，CAE的目标函数为： 是一个超参数控制规则强度。如果是sigmoid encoder： 三个与DAE不同的地方，也有紧密的联系，有小部分噪声的DAE可以看做是一种CAE，当惩罚项在全体重构误差上而不仅仅是encoder上。另外Refai又提出了CAE+H，加入了第三项使得 与 靠近： 注意 CAE学习到的表示倾向于饱和而不是稀疏，也就是说大部分隐层单元靠近极值，它们的导数也很小。不饱和的单元很少，对输入敏感，与权值一起构成一组基表示样本的局部变化。在CAE中，权值矩阵是tied。 7.2.4 Predictive Sparse Decomposition（PSD） (Kavukcuoglu et al., 2008) 提出了sparse coding和autoencoder的变种，叫PSD。 PSD是sparse coding和AE的一个变种，目标函数为： PSD可以看做是sparse coding的近似，只是多了一个约束，可以将稀疏编码近似为一个参数化的编码器。 8.Representation Learning As Manifold Learning PCA就是一种线性流形算法。 8.1 Learning a parametric mapping based on a neighborhood graph 8.2 Learning a non-linear manifold through a coding scheme 8.3 Leveraging the modeled tangent spaces 9. Connections between probabilistic and direct encoding models 标准的概率模型框架讲训练准则分解为两个：log-likelihood 和prior 。 9.1 PSD：a probabilistic interpretation PSD是一个介于概率模型和直接编码方法的表示学习算法 。RBM因为在隐层单元连接的限制，也是一个交叉。但是DBM中就没有这些性质。 9.2 Regularized Auto-encoder Capture Local Statistics of the Density 规则化的AE训练准则不同于标准的似然估计因为他们需要一种prior，因此他们是data-dependent。 (Vincent2011) A connection between score matching and denoising autoencoders Bengio2012_Implicit density estimation by local moment matching to sample from auto- encoders (Refai2012)_A generative process for sampling contractive auto-encoders 规则项需要学习到的表示尽可能的对输入不敏感，然而在训练集上最小化重构误差又迫使表示包含足够的信息来区分他们。 9.3 Learning Approximate Inference 9.4 Sampling Challenge MCMC sampling在学习过程中效率很低，因为the models of the learned distribution become sharper, makeing mixing between models very slow. Bengio2012 表明深层表示可以帮助mixing。 9.5 Evaluating and Monitoring Performance 一般情况下我们在学习到的特征上加一层简单的分类器，但是最后的分类器可能计算量更大（例如fine-tuning一般比学习特征需要更多次数的迭代）。更重要的是这样可能给出特征的不完全的评价。 对于AE和sparse coding来说，可以用测试集上的重构误差来监视。 对于RBM和一些BM， Murray2008 提出用 Annealed Importance Sampling 来估计partition function。RBM的另一种（ Desjardins2011 ）是在训练中跟踪partition function，这个可以用来early stopping和减少普通AIS的计算量。 10. Global Training of Deep Models 10.1 On the Training of Deep Architectures 第一种实现就是非监督或者监督单层训练， Erhan2010 解释了为什么单层非监督预训练有帮助。这些也与对中间层表示有指导作用的算法有联系，例如Semi-supervised Embedding（ Weston2008 ）。 在Erhan2010中， 非监督预训练的作用主要体现在regularization effect和optimization effect上。前者可以用stacked RBM或者AE实验证明。后者就很难分析因为不管底层的特征有没有用，最上面两层也可以过拟合训练集。 改变优化的数值条件对训练深层结构影响很大，例如改变初始化范围和改变非线性函数（ Glorot2010 ）。第一个是梯度弥散问题，这个难题促使了二阶方法的研究，特别是 Hessian-free second-order方法 （ Marten2010 ） 。Cho2011 提出了一种RBM自适应的学习速率。 Glorot2011 表明了sparse rectifying units也可以影响训练和生成的表现。 Ciresan2010 表明有大量标注数据，再合理的初始化和选择非线性函数，有监督的训练深层网络也可以很成功。这就加强这种假设，当有足够的标注样本时，无监督训练只是作为一种prior。 Krizhevsky2012 中运用了很多技术，未来的工作希望是确定哪些元素最重要，怎么推广到别的任务中。 10.2 Joint Training of Deep Boltzmann Machines Salakhutdinov and Hinton (2009) 提出了DBM。 DBM的能量方程： DBM相当于在Boltzmann Machine的能量方程中U=0，并且V和W之间稀疏连接结构。 10.2.1 Mean-field approximate inference 因为隐层单元之间有联系，所以后验概率变得intractable，上文中用了mean-field approximation。比如一个有两层隐层的DBM，我们希望用 近似后验 ，使得 最小。 10.2.2 Training Deep Boltzmann Machines 在训练DBM时，与训练RBM最主要的不同在于，不直接最大似然，而是选择参数来最大化lower-bound。具体见论文。 11. Building-in Invariance 11.1 Augmenting the dataset with known input deformations Ciresan2010 中使用了一些小的放射变换来扩大训练集MNIST，并取得了很好的结果。 11.2 Convolution and Pooling (Le Roux et al., 2008a) 研究了图片中的2D拓扑。 论述这种结构与哺乳类动物的大脑在目标识别上的相同点： Serre et al., 2007 ：Robust object recognition with cortex-like mechanisms DiCarlo et al., 2012 ：How does the brain solve visual object recognition? Pooling的重要性 ： Boureau2010 ：A theoretical analysis of feature pooling in vision algorithms Boureau2011 ：Ask the locals：multi-way local pooling for image recognition 一个成功的pooling的变种是L2 Pooling： Le2010 ：Tiled convolutional neural networks Kavukcuoglu2009 ：Learning invariant features through topographic filter maps Kavukcuoglu2010 ：Learning convolutional feature hierarchies for visual recognition Patch-based Training : (Coates and Ng, 2011) ：The importance of encoding versus training with sparse coding and vector quantization。 这篇文章compared several feature learners with patch-based training and reached state- of-the-art results on several classification benchmarks。 文中发现最后的结果与简单的K-means聚类方法类似，可能是因为patch本来就是低维的，例如边缘一般来说就是6*6，不需要分布式的表示。 Convolutional and tiled-convolutional training: convolutional RBMs： Desjardins and Bengio, 2008 ：Empirical evaluation of convolutional RBMs for vision Lee，2009 ：Convolutional deep belief networks for scalable unsupervised learning of hierarchical representations Taylor，2010 ：Convolutional learning of spatio-temporal features a convolutional version of sparse coding: Zeiler2010 : Deconvolutional networks tiled convolutional networks: GregorLeCun,2010 : Emergence of complex- like cells in a temporal product network with local receptive field Le,2010 : Tiled convolutional neural networks Alternatives to pooling: (Scattering operations) Mallat,2011: Group invariant scattering BrunaMallat,2011 : Classification with scattering operators 11.3 Temporal Coherence and slow features 11.4 Algorithms to Disentanle Facotors of Variantion Hinton，2011 ：Transforming auto-encoders 这篇文章take advantage of some of the factors of variation known to exist in the data。 Erhan，2010 ：Understanding representations learned in deep architectures 这篇文章有实验表明DBN的第二层倾向于比第一层更具有不变性。 12. Conclusion 本文讲述了三种表示学习方法：概率模型、基于重构的算法和几何流形学习方法。 Practical Guide and Guidelines： Hinton，2010 ：Practical guide to train Restricted Bolzmann Machine Bengio，2012 ：Practical recommendations for gradient- based training of deep architectures Snoek2012 ：Practical Bayesian Optimization of Machine Learning Algorithms
准备近期就开始组织一个研读Dictionary Learning论文的讨论组。每周一次，大概１－２个小时，采用Skype的方式。研读的论文主要侧重Dictionary Learning/Sparse Representation，尤其是supervised dictionary learning等。欢迎报名参加（拟５人）。条件是需要在这个方向上发表至少一篇论文。 详细情况请发信给我:zhangzlacademy( a t )gmail.com。请勿发站内信件。
Preliminaries A full-rank matrix A ∈ Rn×m with n m generates an underdetermined system of linearequations Ax = b having infinitely many solutions.Suppose we seek the sparsest solution,i.e., the one with the fewest nonzero entries. Can it ever be unique? If so, when? As optimizationof sparsity is combinatorial in nature, are there efficient methods for finding thesparsest solution? Sparse Solutions of Linear Systems of Equations?. Consider a full-rankmatrix A ∈ Rn×m with n m, and define the underdetermined linear system of equations Ax = b. This system has infinitely many solutions; if one desires tonarrow the choice to one well-defined solution, additional criteria are needed. Hereis a familiar way to do this. Introduce a function J(x) to evaluate the desirabilityof a would-be solution x, with smaller values being preferred. Define the generaloptimization problem (P J ), Selecting a strictly convex function J(·) guarantees a unique solution.Take 2 norm mueasurement as an example, this is given explicitly by Measurement The vector is sparse,if there are few nonzeros among the possible entries in x. It will be convenient tointroduce the 0 “norm” Thus if x0 m, x is sparse. Consider the problem (P0) obtained from the general prescription (P J ) with thechoice J(x) = J 0 (x) ≡ x0; explicitly, Sparsity optimization (2) looks superficially like the minimum 2-norm problem(P 2 ), but the notational similarity masks some startling differences. The solutionto (P 2 ) is always unique and is readily available through now-standard tools fromcomputational linear algebra. (P 0 ) has probably been considered to be a possiblegoal from time to time for many years, but initially it seems to pose many conceptual challenges that have inhibited its widespread study and application. These are rootedin the discrete and discontinuous nature of the 0 norm; the standard convex analysisideas which underpin the analysis of (P 2 ) do not apply. Many of the most basicquestions about (P 0 ) seem immune to immediate insight: • Can uniqueness of a solution be claimed? Under what conditions? • If a candidate solution is available, can we perform a simple test to verifythat the solution is actually the global minimizer of (P 0 )? Perhaps, in some instances, with very special matrices A and left-hand sides b, waysto answer such questions are apparent, but for general classes of problem instances(A, b), such insights initially seem unlikely. From above figure, only the norm are eque or less than 1,the intersection point is on the axises. so we can present it use only one nonzore.On the other hand, the norm which eque or lager than one can see as an convex optimation problem. If 0 norm solution is hard to obtain, we can use 1 norm to be an alternate way. The proof about the equivalency of zero norm and one norm problem can find in . Two ways to get the sparse solution. (1) Greedy Algorithm-OMP (2) Basis Pursuit-IRLS,LARS,Feature-sign search algorithm . Reference: A. M. Bruckstein, D. L. Donoho, and M. Elad, “From sparse solutions ofsystems of equations to sparse modeling of signals and images,” SIAMReview, vol. 51, no. 1, pp. 34–81, 2009. Y.C. Pati, R. Rezaiifar, and P.S. Krishnaprasad, "Orthogonal matching pursuit: Recursivefunction approximation with applications to wavelet decomposition," in Proceedings of the27th Asilomar Conference on Signals, Systems and Computers, Vol. 1, 1993, pp. 40–44. H. Lee, A. Battle, R. Raina and Andrew Y.Ng, "Efficient sparse coding algorithms" in In NIPS, 2007.
原文：不好意思，没有找到原文作者的博客 压缩传感不是万能的， 虽然它是信号和图像处理领域最热门的研究对象 但是它不可能解决所有问题 就像中科院李老师的话： “压缩感知根植于数学理论，它给目前国内浮躁的学术环境提了一个警钟！因为只有很好地钻研它的基本理论和方法，才能将其有效地应用在所关心的问题中；否则它只能是一剂春药，一种无法名状的春药！” ------------------------------------------------------------------------------------------ 人们习惯于用正交基来表示信号，直到最近几十年，人们才发现用冗余的基元素集合来表示信号能够取得更好的结果，当然我们追求的肯定是用最小数量的基元素来最优的表示信号，这就出现了信号的稀疏表示。 L1范数最小化最早并不是Donoho提出的，早在80年代，Fadil Santosa 和William Symes就曾提出了L1范数的最小化，而Donoho提出Compressed sensing 并不是换汤不换药，CS并不是解决信号在一个完备集里面的最优表示问题的，而是提出了一种新的信号采集或者测量方式，这种新的测量方式打破了Shannon-Nyquist定理在信号处理领域一手遮天的局面，已经提出，就引起了相关领域大批学者的关注。Shannon-Nyquist采样定理要求在信号的采集阶段以高于信号带宽的两倍采样率来获取信号，信号才能得到完美的重构，而CS则对信号的带宽不再作要求，取而代之的是稀疏性，满足条件的信号则可在远少于SN采样率的情况下精确的重构信号。 从数学上来说，CS是在一定的条件下求解欠定(不适定)方程，条件包括x要是稀疏的，测量矩阵要满足RIP条件，那么欠定(不适定)方程就会以很大的概率有唯一解。 ------------------------------------------------------------------------------------------- 《Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information》 1.文章告诉我们压缩传感在图像领域的发展源于作者在医学图像领域--MR图像重构得到的惊人结果，接着提出了压缩传感的数学模型，即当一信号在时域具有稀疏性的前提下，对频域进行少量样本的随机抽样，就可以对信号进行重构，作者事实上是从一个特例开始讨论的，即B1是简单的抽样基，B2是傅里叶基，到了文章的结尾，才对这一事实进行扩展，而且上来就是全变分模型，而不是抽象的L1范数最小化。 2.接着作者提出了两个问题：哪一类的信号才可以得到完美的重构，以及，重构时对采样数目的要求到底是什么，作者用定理1.3回答了以上问题，具有T稀疏性的信号，如果采样数满足。。。要求，那么信号可以得到重构，并且可以证明，重构是唯一的而且是最优的。最优性指的是，没有其他的算法可以用更少的采样数目得到这样的结果。 3.作者阐述了压缩传感与测不准原理的关系，并且提出了新的更强的准则。 4。压缩传感与相关研究的联系：利用L1范数最小化来恢复稀疏信号并不是压缩传感的新创，由来已久，其外，压缩传感与信号的稀疏分解具有很深的渊源，从某种意义上说，他们是相同的，当然他们具有本质上的不同：压缩传感是从不完整的数据中恢复信号，而稀疏分解是找到信号的最稀疏最有效的表达，最后作者从信号采样的角度告诉我们文章的最大贡献是提出了一种新的信号采样方式：数目更少，随机性。 5.文章花了大部分的篇幅来证明解的唯一性，在最后，给出了算法的稳定性，鲁棒性，以及算法的扩展，信号具有T稀疏，且采样数目满足定理要求，算法是稳定的，鲁棒性在相关的文章讨论，扩展指的是信号可以在更多的基里面具有稀疏性，不局限于时域和频域，且采样矩阵也可以有更加多样的选择。 ------------------------------------------------------------------------------------------- 1-On theory of compressive sensing via ell1 minimization Simple derivations and extensions 作者信息：Rice,Yin Zhang:http://www.caam.rice.edu/~zhang/ 该文首先指出目前的CS理论有两大部分构成：recoverability和stability,recoverability指的是，什么样的采样矩阵和恢复算法能够重构k稀疏信号，而stability指的是当出现信号的近似k稀疏或者出现观测噪声时，算法的鲁棒性。本文的主要的contributions包括：1）提出了一种全新的non-RIP的分析框架；2）与RIP类算法相比，该算法能够将任意形式的先验信息融合到CS理论中；3）文章还验证了随机矩阵本质上是一致的。 2-Instance-optimality in probability with an ell1 decoder 作者信息：Department of Mathematics University of South Carolina ronald devore： http://www.math.sc.edu/~devore/ 该文…… 3-Incoherent dictionaries and the statistical restricted isometry property 作者信息:Tel-Aviv University Shamgar Gurevich: http://math.berkeley.edu/~shamgar/ 这个大牛的文章太深奥，纯的数学 4-On verifiable sufficient conditions for sparse signal recovery via ell-1 minimization 作者信息：未找到 文章直接指出现有的RIP或者其他的包括Restricted Eigenvalue assumption 和Restricted Correlation assumption都不能立即判定一个矩阵是否能适合L1范数最小化来精确重构信号，因为这些指标都是不可计算的都属于NP问题，而唯一的可计算的指标：Mutual Incoherence又过于保守。该文提出了一种新的量化指标来定量描述给定的矩阵是否足够好来适合L1范数最小化来重构信号。 5-The secrecy of compressed sensing measurements 作者信息：Draper Laboratory，Yaron rachlin： http://yaron.rachlin.googlepages.com/ 该文讨论了CS理论在密码学中应用的可行性，作者主要集中在L1范数最小化算法且无噪声的情况，结论是利用CS并不能得到完美的密码，但是作者阐释了一种称为computational notion of secrey,并说明了CS的measurment可以考虑作为密码。 6-Toeplitz compressed sensing matrices with applications to sparse channel estimation 作者信息：Rice University，Javis Haupt： http://www.ece.rice.edu/~jdh6/ 该文前边部分对CS做了很好的综述，包括介绍CS的几种情况：最简单的CS，近似稀疏信号的CS重构，含Gaussian观测噪声的CS恢复算法，含有限噪声的CS恢复算法。特别是最后两种的区别，文章给了很好的解释和说明，包括相应的算法的各自特点。 7-On recovery of sparse signals via ell1 minimization 作者信息：The Wharton School University of Pennsylvania t.tony cai： http://www-stat.wharton.upenn.edu/~tcai/ 这篇文章是对candes及Donoho的方法的改进，作者将问题进行了不同的分类，包括无噪声，有限噪声及高斯噪声三种情况，然后讨论了两种重构模型：DantZig Selector和L1 minimation with L2 constraints,主要的改进之一是提出了更弱的条件，使得可以重构的信号范围进一步扩大。通常我们用RIP性质，或者MIP性质来验证矩阵是否能用来作为一个采样矩阵，文章对这两个条件进行了讨论，并分析了他们之间的关系。作者只是将一个更弱的条件用到这三种情况下，不过作者主页上还是可以看到，09年作者做了相当多的工作。 8-Deterministic designs with deterministic guarantees Toeplitz compressed sensing matrices sequence design and system identification 作者信息：Boston University Department of Electrical and Computer Engineering venkatesh saligrama： http://iss.bu.edu/srv/ 该文应该属于CS在无线通讯领域的应用，以前的满足RIP性质的采样矩阵一般都是满足特定分布的随机矩阵，最近才逐渐出现确定元素构成的采样矩阵，本文作者根据该领域的特殊要求，构造了特别的采样矩阵，并证明了其满足RIP性质。 9-Compressive sensing by random convolution 作者信息：Georgia Tech，Justin Romberg： http://users.ece.gatech.edu/justin/Justin_Romberg.html 该文提出了一种全新的CS框架：先与随机的波形元素进行卷积，然后在时域内进行降采样，从而得到观测值。作者在文章中说明了这种方法是一种通用有效的稀疏数据观测方式，并用radar和Fourier optics两种应用情景来说明这种观测方式能够让我们得到分辨率更高的结果，但是这个框架的通用性还是值得进一步的探究。个人认为作者对信号的稀疏性解释的非常详细，并且分别将稀疏度与带宽对应，采样需求数目与采样频率对应。作者对以前的随机采样矩阵进行了分类：每个元素服从于某种分布；随机从某正交基中抽取m行作为采样矩阵，并从通用性和计算量上对两种矩阵进行了对比。作者还提出了三个考量采样系统的指标：通用性，计算量，以及物理可实现性。 10-Compressed sensing over the Grassmann manifold A unified analytical framework 作者信息：Caltch，Weiyu Xu： http://mathbaby.spaces.live.com/ 该文指出，满足RIP的采样矩阵能够恢复出稀疏信号，只是一个充分条件，作者基于高维几何，提出了更加紧的充要条件，而算法的目标也很明确：近似稀疏信号（作者给出了很特别的定义：基于L1范数）； 11-Combining geometry and combinatorics A unified approach to sparse signal recovery 作者信息：MIT，Radu Berinde： http://people.csail.mit.edu/radu/ 该文对采样矩阵和恢复算法进行了分类：基于组合的方法和基于几何的方法，并且相应的算法有相应的采样矩阵与其相对应，组合的方法通常对应于稀疏的二值矩阵，而几何的方法主要是指常用的l1范数最小化等，对应的矩阵为稠密的随机高斯随机贝努力矩阵。文章从整体的观点出发，认为两种方法在某种意义下是相同的，并提出了新的采样矩阵和恢复算法。 12-High-dimensional subset recovery in noise Sparsified measurements without loss of statistical efficiency 作者信息:UC Berkeley,Dapo Omidiran: http://www.eecs.berkeley.edu/~dapo/ 该文同上篇文章一样，也是研究了基于稀疏采样矩阵的Losso算法，同时考虑采样矩阵的稀疏和观测样本的噪声，并证明了当采样矩阵的稀疏度趋于0的情况下所需要的采样数目与稠密的采样矩阵需要的相同。 13-Efficient compressed sensing using high quality expander graphs 作者信息：Princeton，sina Jafarpour： http://sina2jp.googlepages.com/sinajafarpour%27shomepage 该文起源于Coding Theory，用于error correcting,其中比较经典的error correcting codes是LDPC（Low Density Parity Codes）,随后被xu weiyu（加州理工）用于CS领域，这篇文章是对Xu的理论的改进。 常用的RIP性质被用来检验一个随机矩阵是否能够用来作为采样矩阵，从而使得L1范数最小化算法能够对稀疏信号进行完美的重构，满足RIP性质的矩阵可以作为采样矩阵（充分条件），而Radu（见本页第一篇文章）提出了一种新的RIP，called RIP-1，标准的RIP（也称:RIP-2）保持了两稀疏信号的欧氏距离即Norm2，而RIP-1，则保持了稀疏信号的Manhattan距离，即Norm1，作者在文中说明了，只要矩阵满足RIP-1，也能保证将稀疏信号完美重构。 14-On some deterministic dictionaries supporting sparsity 作者信息：（特拉维夫，以色列港市）Shamgar Gurevich： http://math.berkeley.edu/~shamgar/ 作者系数学出身，这篇文章从语言到内容涉及到太多的数学内容，可略过。 15-A remark on compressed sensing 中提到：关于采样矩阵需要满足的条件，首先是由D.Donoho在文Compressive Sensing中提出的CS1-CS3条件，接着E.Candes,J.Romberg,T.Tao也独立的证明了矩阵需要满足的条件，进一步的研究，由A.Cohen,W.Dahmen,R.Devore(Compressed Sensing and k-term approximation)中完成，而这篇文章主要的工作就是证明了在渐进的情况下，即当m,n趋于无穷大的情况下，以上三个条件是一致的。 16-Toeplitz structured compressed sensing matrices： 又是一篇关于采样矩阵的文章，这篇文章提出了一种新的构造采样矩阵的方法，Toeplitz Matrix,并且证明了改矩阵满足Cades提出的RIP性质，列出了与通常的随机采样矩阵相比的优缺点，以及该采样矩阵在系统辨识中的应用。 17-Efficient compressive sensing with determinstic guarantees using expander graphs 这篇文章很好，一个原因是它将07年之前的关于压缩CS的文章进行了很好的总结，综述内容很丰富，此外是该文提出了一种新的框架，一种基于bipartite expander graphs的方法，利用图论来解决CS的问题，最终回答了作者提出的两个CS存在的问题：1.对于O（n），及k=O（n）的情况，目前的CS理论是否能够精确重构，2.如果能的话，信号满足稀疏性的前提下，这样的矩阵及重构算法是否存在？ 18-Computation and relaxation of conditions for equivalence between ell1 and ell0 minimization 这篇文章证明了在什么情况下，l0和l1的解是相同的，而且对信号的稀疏性有什么要求。 19-Fast compressive sampling with structurally random matrices 该文首先分析了已有的采样矩阵所具有的四个重要特征，并指出目前的采样矩阵一般只具备其中部分特征，之后具体分析的现在流行的两类采样矩阵的优缺点，包括第一类：随机高斯，随机贝努力，及亚高斯阵，第二类：部分傅里叶阵以及部分正交阵。在分析的基础上提出了一个hybrid采样矩阵，证明了该采样矩阵能够同时具有上述四个特点。 20-Sparse recovery using sparse random matrices 作者来自MIT,http://people.csail.mit.edu/radu/,主要研究方向也就是CS，文章的综述不错，总结的很详细，实验也很不错，文章主要是对稀疏的采样矩阵与通常的随机采样矩阵的对比，及其优势，并通过丰富的实验对几种常用的采样矩阵进行了比较。 21-A negative result concerning explicit matrices with the restricted isometry property 正如题目所示：文章指出通常的0，1采样矩阵需要额外的条件才能满足最优性，并且给出了更加紧的满足RIP条件的结果。 22-Toeplitz block matrices in compressed sensing 同样是讨论采样矩阵文章。
It is clear that presentations to governors, mayors and emergency management directors using maps must be cogent, direct and succint. Does the new visualization tools with simple pin or thematic maps are taking precedent over more in depth spatial analysis?
标签: representation
