Seminar Details
2012-09-25 (14.00) : Randomly sampling rows from orthonormal matrices, with application to least squares problems
At Euler building
Organized by Mathematical Engineering
Speaker :
Ilse IPSEN (North Carolina State University )
Abstract :
The Blendenpik algorithm is a fast method for solving least squares
problems for matrices A of full column rank. Blendenpik consists of the preconditioned iterative solver LSQR, where the preconditioner is obtained by randomly sampling rows of A.
We show that the condition number of the preconditioned matrix can be determined by randomly sampling rows from a specific matrix Q with orthonormal columns. We consider two sampling strategies, and present different probabilistic bounds for the condition numbers of the sampled matrices. Our bounds depend on the coherence of Q, or on its leverage scores. Numerical experiments confirm the accuracy of the bounds, even for small matrix dimensions.