4Linear Regression

This chapter focuses on the (tall) linear regression problem.

Direct Methods¶

Classical direct solvers for Linear Regression such as the LAPACK method underlying np.linalg.lstsq work in two stages. First, $\vec{A}$ is factorized (e.g QR factorization). Second, the factorization is used to solve the linear system. When implemented properly, such algorithms are numerically stable and require $O(nd^2)$ operations. However, the dominant cost of this approach is computing a matrix factorization which, as we have seen in our discussion on the cost of linear algebra, does not have a particularly high flop-rate. Moreover, the total number of flops is $O(nd^2)$, which might be too expensive when $n\gg d \gg 1$.

Iterative Methods¶

Iterative methods such as LSQR begin with an initial guess $\vec{x}_0$ and iteratively produce a sequence of approximate solutions $\vec{x}_1,\ldots,\vec{x}_t$, where ideally $\vec{x}_k$ is close to the solution of Linear Regression. At each iteration, such methods perform a matrix-vector product with $\vec{A}$ and $\vec{A}^\T$, in addition to some vector operations. Thus, the matrix-vector products are typically the dominant cost, and require $O(\nnz(\vec{A})) \leq O(nd)$ operations per iteration. While iterative methods are able to take advantage of sparsity in $\vec{A}$, they may require many iterations to converge when $\vec{A}$ is ill-conditioned problems.

Further Reading¶

• Sarlos (2006), Rokhlin & Tygert (2008): Early works in RandNLA that respectively introduce sketch-and-solve and sketch-and-precondition.

• Clarkson & Woodruff (2013), Chenakkod et al. (2024),Chenakkod et al. (2025): Line of work in TCS on sparse sketches that give algorithms for regression that run in time close to the optimal $O(\nnz(\vec{A}) + d^{\omega})$.

• Epperly (2024), Epperly et al. (2025): Line of work on the stability fo sketch-and-precondition type algorithms