# How to use a preconditioner estimated from a subset of data?

Suppose I'm solving $$Ax=b$$ using row-action method like Kaczmarz for $$m\times n$$ matrix A with $$m\approx \infty$$ and have $$H_k=\frac{1}{k}A_k^T A_k$$ which is an estimate of the Hessian obtained from random $$k$$ rows of $$A$$.

How should I use $$H_k$$?

The problem of diving by $$H_k$$ is that it appears to underestimate the variance of $$H_\infty$$ in directions of bottom eigenvectors of $$H_k$$. Realistically, only first $$K-1$$ directions may have an accurate estimate and normalizing in direction $$K$$ is numerically unstable. Natural approach is precondition using $$H_k+\epsilon I$$ or by using first $$K$$ factors of truncated SVD of $$H_k$$. How to choose $$\epsilon$$ or $$K$$?

Here's an experiment I did, for $$n=784$$ and $$k=60000$$, I can estimate $$H_k$$ using $$60,000$$ random rows, and evaluate it on a different set of $$10,000$$ rows. Eyeballing the graph shows that blow-up starts to happen around $$K=600$$.

Additionally, I tried with $$k=1000$$ and similarly found that I only first $$K=320$$ directions have an accurate estimate of variance.

Is there a more rigorous way of obtaining these cutoffs?  • I can't speak to this specific application, but the typical way of choosing $K$ for the truncated SVD is to pick some tolerance $\eta$ and let $K$ be the largest integer such that $$\frac{\sum_{i=K}^n \sigma_i^2}{\sum_{i=1}^n \sigma_i^2} < \eta$$ is true. This can be rewritten in many ways but it boils down to "Choose the smallest $K$ that represents the $1-\eta$ fraction of the variance. Nov 20 at 19:17
• Given $\eta$ I can choose $K$, then question is then -- how to pick $\eta$? Because $H_k$ is estimated from $k$ samples, $\eta$ should depend on $k$ somehow Nov 20 at 19:23
• In my experience, people either just choose $\eta$ small, e.g., $10^{-2}$, or they plot the singular values of the matrix and look for where a large drop in the magnitude of the singular values occurs and truncate there. Nov 20 at 19:26