Mathematics – Numerical Analysis
Scientific paper
2012-03-21
Mathematics
Numerical Analysis
21 pages, 6 figures, 5 algorithms
Scientific paper
We consider two strategies for sampling rows from m by n matrices Q with orthonormal columns. The first strategy samples c rows with replacement, while the second one treats each row as an i.i.d. Bernoulli random variable, and samples it with probability \gamma = c/m. We derive several bounds for the condition numbers of the sampled matrices and express them in terms of the coherence, \mu, of Q. In particular, we show that for both sampling strategies the two-norm condition number of the sampled matrix SQ is bounded by ((1+\epsilon)/(1-\epsilon))^.5 with probability at least 1-\delta if c\geq 3m\mu ln(2n/\delta)/\epsilon^2. Numerical experiments confirm the accuracy of the bounds, even for small matrix dimensions. We also present algorithms to generate matrices with user-specified coherence, and apply the bounds to the solution of general, full-rank least squares problems with the randomized preconditioner from Blendenpik. A Matlab package, \kappa(SQ), implements the matrix generation algorithms and the two sampling strategies, and plots the condition numbers and the various bounds.
Ipsen Ilse C. F.
Wentworth Thomas
No associations
LandOfFree
The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-489060