2
$\begingroup$

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?

enter image description here

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – whpowell96
    Nov 20 at 19:17
  • $\begingroup$ 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 $\endgroup$
    – Yaroslav Bulatov
    Nov 20 at 19:23
  • $\begingroup$ 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. $\endgroup$
    – whpowell96
    Nov 20 at 19:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.