New studies of randomized augmentation and additive preprocessing

• A standard Gaussian random matrix (hereafter referred to just as Gaussian matrix) 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.