大规模矩阵降维的随机逼近方法

Stochastic Approximation Approaches of Large-scale Matrix Dimension Reduction

大规模矩阵降维和分解是数据分析的核心问题之一,在工程领域应用广泛,如图像分割、文本分类、数据挖掘,然而,传统的矩阵分解方法(如SVD、谱分解)计算复杂度高,不适用于大规模矩阵处理.近些年来,随机逼近方法用来发现大规模矩阵的低维近似,有效地降低了计算复杂度,是当今的研究热点.围绕基于随机逼近的大矩阵降维方法展开论述,介绍了矩阵降维中的抽样策略、CUR分解、Nystrom方法、随机逼近方法,比较研究了这些方法的优缺点.对重要的随机逼近方法开展了一些图像试验分析.最后,进行了总结并讨论了一些方向的可行性.

Large-scale matrix dimension reduction and decomposition are key problems in data analysis and widely applied to image processing, text classification, data mining. How- ever, stochastic low-rank approximation of a large-scale matrix is an ideal choice with low computational complexity and is one of current research focuses. This paper departs from sampling based reduction methods, discusses CUR decomposition, Monte Carlo based sampling, Nystr？m method, stochastic approximation, and points out the advantages and disadvantages of these approaches. Some experiments are carried out on SAR images in terms of important stochastic approximation approaches. At last, we present the possible future directions in matrix dimension reduction.