Publications and Research

Document Type


Publication Date

Spring 2015


We study two applications of standard Gaussian random multipliers. At first we prove that with a probability close to 1 such a multiplier is expected to numerically stabilize Gaussian elimination with no pivoting as well as block Gaussian elimination. Then, by extending our analysis, we prove that such a multiplier is also expected to support low-rank approximation of a matrix without customary oversampling. Our test results are in good accordance with this formal study. The results remain similar when we replace Gaussian multipliers with random circulant or Toeplitz multipliers, which involve fewer random parameters and enable faster multiplication. We formally support the observed efficiency of random structured multipliers applied to approximation, but not to elimination. Moreover, we prove that with a probability close to 1 Gaussian random circulant multipliers do not fix numerical instability of the elimination algorithms for a specific narrow class of well-conditioned inputs. We know of no such hard input classes for various alternative choices of random structured multipliers, but for none of such multipliers we have a formal proof of its efficiency for numerical Gaussian elimination.


31 pages, 7 figures



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.