11

Given two matrices $A$ and $B$, I'd like to find vectors $x$ and $y$, such that, $$ \min \sum_{ij} (A_{ij} - x_i y_j B_{ij})^2. $$ In matrix form, I'm trying to minimize the Frobenius norm of $A - \mbox{diag}(x) \cdot B \cdot \mbox{diag}(y) = A - B \circ (x y^\top)$.

In general, I'd like to find multiple unit vectors $x$ and $y$'s in the form $$ \min \sum_{ij} (A_{ij} - \sum_{k=1}^n s_i x_i^{(k)} y_j^{(k)} B_{ij})^2. $$ where $s_i$'s are positive real coefficients.

This is equivalent to singular value decomposition (SVD) when $(B)_{ij} = 1$.

Does anybody know what this problem is called? Is there a well-known algorithm like SVD for the solution of such problem?

(migrated from math.SE)

Memming
  • 870
  • 1
  • 8
  • 19
  • I believe this is Generalized SVD. The Wikipedia entry isn't very detailed, so you should probably check the linked sources. In particular, page 466 of this Google books link might be helpful. –  Mar 14 '12 at 17:16
  • 1
    To me, this doesn't look anything like the generalized SVD. Particularly since B is not necessarily diagonal or symmetric, so each $x$ or $y$ can appear many times in the sum. – Victor Liu Mar 14 '12 at 19:16
  • B does not need to be diagonal nor symmetric in generalized SVD. Both of the links I provided indicate that A and B can be general complex-valued matrices of dimension M-by-N and P-by-N respectively. –  Mar 14 '12 at 20:22
  • Thanks for the suggestion @EMS. I would appreciate if you can elaborate the connection. – Memming Mar 14 '12 at 22:05

1 Answers1

9

This is far from generalized SVD.

If B is a positive matrix, you can use my package BIRSVD http://www.mat.univie.ac.at/~neum/software/birsvd/

The paper http://www.mat.univie.ac.at/~neum/software/birsvd/svd_incomplete_data.pdf describing the method there also gives references that you may consider to do a literature search.

Arnold Neumaier
  • 11,318
  • 20
  • 47
  • Ah, transforming the problem into weighted low rank approximation! Thanks a lot! – Memming Mar 16 '12 at 22:47
  • To add details to @Arnold's answer, this problem can be transformed into a weighted low rank approximation problem where the objective is to minimize the weighted norm instead of Frobenius norm.

    $||C - \sum s_i \mathbf{x_i} \mathbf{y_i^\top}||^2_W$ where $||C||_W = ||C \circ W||_F$ and $\circ$ denotes the Schur product (aka Hadamard product).

     – Memming Mar 19 '12 at 16:20
  • Yes. This gives a nice name to your problem. How to solve it is a different matter. It is not a standard problem and it was quite tricky to find an algorithm that is both fast and reliable. – Arnold Neumaier Mar 19 '12 at 18:17
  • @ArnoldNeumaier this is great, thank you. would it be possible to get a license and copyright notice with your code? As it is now it is proprietary software. If you release it under GPLv3 or compatible it might find its way to GNU Octave's linear-algebra package. – JuanPi Nov 30 '16 at 07:53