Assume that you have two linear maps $A$ and $V$. For a given $x$ (of appropriate dimension) you can compute $Ax$ numerically, and for any $y$ (of appropriate dimension) you can calculate $V^Ty$ numerically. But you do not have access to both $A^Ty$ and $Vx$ on your computer. Hence, you can compute things like $$\langle Ax,y\rangle\quad\text{and}\quad \langle x,V^Ty\rangle$$ and you may even be able to estimate $$\sup_{x,y}|\langle Ax,y\rangle - \langle x,V^Ty\rangle|.$$

My question is:

Is there a way to reliably compute $\|A-V\|$? (Any norm would be fine, spectral norm desirable. An upper bound would also be ok.)

I'd like to add, that this situation is somehow always the case in floating point arithmetic, because each time you compute A*x or A'*y, different rounding errors occur, hence the results of (A*x)'*y and (x')*(A'*y) are different, too. (Btw, does anybody know an estimate for this quantity?) In double precision, this is probably not much of a problem, but in single or half precision, the errors seem to become non-neglectable.

  • $\begingroup$ Have you looked into randomized numerical linear algebra? If I understood correctly, the issue is that you can never take the full supremum in your estimate, and not even for all in a "nice" subspace for which you have approximation properties? That seems like a similar situation to me. $\endgroup$ – Christian Clason Sep 14 at 13:05
  • $\begingroup$ Sounds natural - do you have a specific entry point in mind? $\endgroup$ – Dirk Sep 14 at 13:42
  • $\begingroup$ A natural starting point would be cambridge.org/core/journals/acta-numerica/article/…, and there's also arxiv.org/abs/1608.04481 and arxiv.org/abs/2002.01387. You could also specifically look at a randomized SVD, which you could compute for $A-V$ based on what you have and should give you (an estimate of) the spectral norm. $\endgroup$ – Christian Clason Sep 14 at 13:49
  • $\begingroup$ Thanks! Will look! An SVD of $A-V$ seems hard to if can't apply neither $A^T$ nor $V$... $\endgroup$ – Dirk Sep 14 at 17:05
  • $\begingroup$ Oh, you need to combine it with an iterative scheme such as the Golub-Kahan-Lanczos bidiagonalization. (But maybe you could add a bit of background on your situation where you can compute $\langle Ax,y\rangle$ without computing $Ax$... You don't mention whether your linear mappings are finite- or infinite-dimensional, for example.) $\endgroup$ – Christian Clason Sep 14 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.