Faster Least Squares Approximation

Details Faster Least Squares Approximation Faster Least Squares Approximation

2007-10-07

arxiv.org/abs/0710.1435v4

Computer Science

Data Structures and Algorithms

25 pages; minor changes from previous version; this version will appear in Numerische Mathematik

Scientific paper

Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets $n$ be the number of constraints and $d$ be the number of variables, with $n \gg d$. Then, existing exact methods find a solution vector in $O(nd^2)$ time. We present two randomized algorithms that provide very accurate relative-error approximations to the optimal value and the solution vector of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with the Randomized Hadamard Transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, solving the smaller problem provides relative-error approximations, and, if $n$ is sufficiently larger than $d$, the approximate solution can be computed in $O(nd \log d)$ time.

Affiliated with

Also associated with

No associations

Rating

Faster Least Squares Approximation 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 Faster Least Squares Approximation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Least Squares Approximation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-300913