TR-2013001: Randomized Augmentation and Additive Preprocessing

Random matrices tend to be well conditioned, and so one can expect that appending properly 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 random sparse and structured matrices, defined by much fewer random parameters. For sample applications of randomized preprocessing to matrix computations, we precondition an ill conditioned 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 diagonalization. Combining our present techniques with randomized matrix multiplication (which we study elsewhere) should lead to further progress in matrix computations. 2000 Math. Subject Classification: 15A52, 15A12, 65F22