4
$\begingroup$

I have a linear system of the form $A x = b$ where $A$ and $b$ are known, $A$ is "square", and $\lvert b \rvert_1 = \lvert x \rvert_1 = 1$. Unfortunately, I am working in a framework that only gives me access to a dot product, not the individual vector or operator elements. The only way I have found to solve this problem is by optimizing the quantity:

$$ d^2 = \lvert b - A x \rvert_2 = \langle b, b \rangle - 2 \langle b, A x \rangle + \langle A x, A x \rangle $$

subject to the normalization $\lvert x \rvert_1 = 1$. This tends to work, but it becomes computationally challenging to compute the last term because of the double operator. (Forming the vector $A x$ is actually very difficult, so I have to compute the inner product "all at once" to use this toolset: $\langle A x, A x \rangle = x^T A^T A x$.)

Now, if this were an $L^2$ constrained problem, I could use ${d^\prime}^2 = 1 - \langle b, A x \rangle$ as the "overlap" between states $b$ and $A x$, which makes more sense to me coming from a quantum mechanics perspective, yet, because $x$ is only $L^1$ normalized, I would still have to ensure that $b$ and $A x$ are $L^2$ normalized before optimizing this way -- which takes me back to computing $\langle A x, A x \rangle$ at every step, which is, again, too expensive. The operator $A$ does guarantee that the $L^1$ norm is preserved, but the $L^2$ norm is, in general, not.

I can't think of another approach to solve this equation using only inner products. Have I missed something obvious? Or is there literature out there about solving this problem? Google has yet to be helpful on this issue, because "$L^1$ optimization" is a common search and does not seem to be related to my question, since $A$ in that problem is apparently sparse. Please explain any answers at an advanced-undergrad-core-math level, because I am not a mathematician.

$\endgroup$
8
  • $\begingroup$ In principle using products like $\langle e_i, A e_j \rangle$ can be used to reconstruct $A_{i,j}$, similar for $b_i$; after that solve it the usual way. $\endgroup$ – Maxim Umansky Oct 21 '20 at 22:32
  • $\begingroup$ @MaximUmansky Thanks for the suggestion. I'm actually working with objects that have been decomposed using tensor train decomposition, so they are typically far too large to actually store reconstructed like that. $\endgroup$ – emprice Oct 21 '20 at 22:38
  • $\begingroup$ How about using the Krylov method (GMRES) for it? It needs only products that are available to you. $\endgroup$ – Maxim Umansky Oct 21 '20 at 22:42
  • $\begingroup$ @MaximUmansky I had thought about that... But doesn't the Krylov method require a lot of inner products and compression steps to keep the ranks under control? $\endgroup$ – emprice Oct 21 '20 at 22:44
  • $\begingroup$ Well, GMRES is one of leading methods for large sparse matrices; depending on the sparsity structure of your matrix, it could be a good way to deal with it anyway, even if it was fully accessible. $\endgroup$ – Maxim Umansky Oct 21 '20 at 22:58

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.