Faster least squares approximation (Q623334)

It is well-known that an approximate solution \(x_{opt}\) of an overdetermined system of linear equations \[ Ax = b, \quad A \in \mathbb{R}^{n \times d}, \quad b \in \mathbb{R}^n, \quad n \geq d, \tag{1} \] is commonly found by the method of least-squares solving the optimization problem \[ Z = \min_{x \in \mathbb{R}^d} {\| Ax-b \|}_2 \] by direct methods, such as QR decomposition, in \(O(nd^2)\) time. The authors now present two randomized algorithms with which one can compute an accurate relative-error approximation \({\tilde x}_{\text{opt}}\) to the Euclidian norm solution vector \(x_{\text{opt}}\) for a large class of overdetermined least-squares problems, i.e., for \(n \gg d\), \(n < e^d\), in \(O(nd \ln d)\) time. In particular, the authors prove the following main theorem (Theorem 1 in the paper): Suppose (1), and let \(\varepsilon \in (0,1)\). Then, there exists a randomized algorithm that returns a vector \({\tilde x}_{\text{opt}} \in \mathbb{R}^d\) with probability at least 0.8, such that the following two claims hold: {\parindent=6mm \begin{itemize}\item[(a)]\({\|A{{\tilde{x}}_{\text{opt}}} - b \|}_2 \leq (1 + \varepsilon) Z\), \item[(b)]\(\| x_{\text{opt}} - {\tilde x}_{\text{opt}}\|_2 \leq \sqrt{(\varepsilon)} \kappa(A) \sqrt{{\gamma}^{-2}-1} \|x_{\text{opt}}\|_2\), \end{itemize}} where \(\kappa(A)\) is condition number of \(A\) and \(\gamma \in [0,1]\) is the fraction of the norm of \(b\) that lies in the column space of \(A\). Then the authors formulate the two randomized algorithms and prove that the claims of the main theorem are fulfilled. Both algorithms preprocess the data with the randomized Hadamard transform, introduced by \textit{N. Ailon} and \textit{B. Chazelle} [``Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform,'' Proceedings of the 38th Annual Symposium on Theory of Computing, 557--563 (2006)]. Roughly speaking, after the multiplication of \(A\) and \(b\) by the matrix product of the randomized Hadamard transform the first algorithm samples uniformly \(r\) constraints from the preprocessed problem and exactly solves the smaller \(r \times d\) least-squares problem getting the approximate solution \({\tilde x}_{\text{opt}}\) that fulfills the claims of the main theorem. A formula for \(r\) is provided. The second algorithm also constructs a smaller problem using a projection-based randomized algorithm with the help of a well-defined sparse matrix (sparse projection). It should be mentioned that both algorithms practically compute only those rows of the preprocessed matrix and only those elements of the right-hand sides that need to be accessed. For the empirical performance the authors refer to publications in which real world examples are provided using algorithms that are based on the ideas of this paper.