Randomized Augmentation and Additive Preprocessing

Random matrices tend to be well conditioned, and so one can expect that appending prop-erly scaled random rows and columns or adding a scaled random matrix of a fixed rank can decrease the condition number of an ill conditioned matrix. We prove probabilistic estimates for this decrease by using Gaussian random matrices as the preprocessors, but our tests showed equally strong impact on the condition numbers in the case where the preprocessors were ran-dom sparse and structured matrices, defined by much fewer random parameters. For sample applications of randomized preprocessing to matrix computations, we precondition an ill condi-tioned matrix, approximate its singular spaces associated with its largest and smallest singular values, approximate this matrix with low-rank matrices, and yield its 2 × 2 block diagonaliza-tion. Combining our present techniques with randomized matrix multiplication (which we stud