11
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user563
    Commented Mar 14, 2012 at 17:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Victor Liu
    Commented Mar 14, 2012 at 19:16
  • $\begingroup$ 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. $\endgroup$
    – user563
    Commented Mar 14, 2012 at 20:22
  • $\begingroup$ Thanks for the suggestion @EMS. I would appreciate if you can elaborate the connection. $\endgroup$
    – Memming
    Commented Mar 14, 2012 at 22:05

1 Answer 1

9
+50
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Ah, transforming the problem into weighted low rank approximation! Thanks a lot! $\endgroup$
    – Memming
    Commented Mar 16, 2012 at 22:47
  • $\begingroup$ 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). $\endgroup$
    – Memming
    Commented Mar 19, 2012 at 16:20
  • $\begingroup$ 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. $\endgroup$ Commented Mar 19, 2012 at 18:17
  • $\begingroup$ @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. $\endgroup$
    – JuanPi
    Commented Nov 30, 2016 at 7:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.