6
$\begingroup$

What is the best known complexity for finding a vector $x \in \mathbb{R}^n$ to minimize $||Ax - b||^2$ and/or to solve (when possible) the system of linear equations $Ax=b$?

I am interested in approximation methods that produce $\epsilon$-approximations for arbitrarily small $\epsilon>0$. Specifically, if $A$ is a real-valued $m \times n$ matrix and $b$ a column vector of size $m$, if I can get an answer within $\epsilon$ of optimality via an algorithm that has total complexity $O(mn \log(mn/\epsilon))$, is that good? Or known?

Any related thoughts or references are appreciated.

Some basic comparisons:

i) $O(mn \log(mn/\epsilon))$ seems to be better than Gaussian elimination, which can have higher complexity and has “divide by small number” issues.

ii) The least-square problem of minimizing $||Ax-b||^2$ is the same as finding a vector $x$ to solve the orthogonality equations $A^TAx = A^Tb$, and these orthogonality equations always have (possibly many) solutions $x \in \mathbb{R}^n$. Yet, computing $A^TA$ requires $mn^2$ computations, which is already larger than $O(mn\log(mn/\epsilon))$ (assuming we overlook the log() factors).

iii) Gauss-Seidel iterative methods seem nice but I think (I am not sure) these methods need matrices to be square and to have special structure.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Comment for ii): You can solve $A^TAx=A^Tb$ by CG without even forming $A^TA$ (side note: contrary to the widespread believe this is not such a bad idea, even for ill-conditioned matrices, since the convergence of CG is more influenced by the clustering of the singular values and not only by it condition number). $\endgroup$
    – Dirk
    Commented Jul 12, 2016 at 11:50

1 Answer 1

Reset to default
4
$\begingroup$

There is a meaningful oracle model where you can obtain a provably optimal method when searching for approximate solutions: this is the "matrix-vector multiplication oracle", where you want to solve a linear system $Ax=b$ with the minimum number of products of the form $Ax$ or $A^Ty$ (that's what the oracle provides).

In this model, one can prove that the conjugate gradient method is the best you can do in many (if not all) situations. For example, when you have an upper bound on the eigenvalues of $A^TA$, say $L$, then the number of iterations is $O(\sqrt{LR^2/\varepsilon})$, where $R>0$ is the distance to the solution from your starting point. Also, if you have upper and lower bounds on the spectrum you can get linear convergence (that is, logarithmic dependence on $\varepsilon$) for conjugate gradients, and the speed of this linear convergence is optimal (this is the square root of the condition number).

For more on this, check Chapter 12 on Nemirovski's book (http://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf), or for a short version Vishnoi has these nice lecture notes (http://theory.epfl.ch/vishnoi/CargeseLectures.pdf).

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .