New Studies of Randomized Augmentation and Additive Preprocessing
New Studies of Randomized Augmentation and Additive Preprocessing
复制标题
随机增强和加性预处理的新研究
DOI：
10.1016/j.laa.2016.09.035
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Liang Zhao
中科院分区：
文献类型：
--
作者：
V. Pan;Liang Zhao
·标准高斯随机矩阵（以下简称为高斯矩阵）具有概率为1的满秩，并且是良好条件的，概率非常接近1，并且随着矩阵偏离正方形形状并变得更加矩形，快速收敛到1。·如果我们将足够多的高斯行或列附加到任何归一化且可能秩不足或病态的矩阵，则增广矩阵具有满秩的概率为1，并且是良态的概率接近1。·我们指定并证明了增广的这些性质，并将它们扩展到加法预处理，即添加两个矩形高斯矩阵的乘积。·通过将我们的随机化技术应用于具有数值秩r的矩阵，我们加速了用于逼近其尾部奇异空间的已知算法，该尾部奇异空间与其所有正奇异值（r个最大值除外）相关联。·我们的算法使用更少的随机参数和运行速度更快时，各种随机稀疏和结构化的预处理器取代高斯。根据经验，结果算法的输出与高斯预处理下的输出一样精确。·我们新颖的对偶技术为这些经验观察提供了迄今为止缺失的正式支持，并为我们的预处理的去随机化以及通过使用更有效的稀疏和结构化预处理器进一步加速和简化我们的算法打开了大门。我们的技术和我们的进展可以应用到其他各种基本的矩阵计算，如著名的低秩近似矩阵随机抽样的手段。
•A standard Gaussian random matrix (hereafter referred to just asGaussianmatrix) has full rank with probability 1 and is well-conditioned with a probability quite close to 1 and converging to 1 fast as the matrix deviates from the square shape and becomes more rectangular.•If we append sufficiently many Gaussian rows or columns to any normalized and possibly rank deficient or ill-conditioned matrix, then the augmented matrix has full rank with probability 1 and is well-conditioned with a probability close to 1.•We specify and prove these properties of augmentation and extend them to additive preprocessing, that is, to adding a product of two rectangular Gaussian matrices.•By applying our randomization techniques to a matrix that has numerical rank r, we accelerate the known algorithms for the approximation of its trailing singular spaces, associated with all its positive singular values, except for the r largest values.•Our algorithms use much fewer random parameters and run much faster when various random sparse and structured preprocessors replace Gaussian. Empirically the outputs of the resulting algorithms are as accurate as the outputs under Gaussian preprocessing.•Our novel duality techniques provides formal support, so far missing, for these empirical observations and opens door to de-randomization of our preprocessing and to further acceleration and simplification of our algorithms by using more efficient sparse and structured preprocessors.•Our techniques and our progress can be applied to various other fundamental matrix computations such as the celebrated low-rank approximation of a matrix by means of random sampling.