problema SVD ponderado?

Dadas duas matrizes e , eu gostaria de encontrar os vetores e , de modo que, Em forma de matriz, estou tentando minimizar a norma Frobenius de . $A$ $B$ $x$ $y$

min \sum_{i j} (A_{i j} - x_{i} y_{j} B_{i j})^{2} .

$\min \sum_{ij} (A_{ij} - x_i y_j B_{ij})^2.$

A - diag (x) \cdot B \cdot diag (y) = A - B \circ (x y^{⊤})

$A - \mbox{diag}(x) \cdot B \cdot \mbox{diag}(y) = A - B \circ (x y^\top)$

Em geral, eu gostaria de encontrar vários vetores unitários $x$ e $y$ no formato

min \sum_{i j} (A_{i j} - \sum_{k = 1}^{n} s_{i} x_{i}^{(k)} y_{j}^{(k)} B_{i j})^{2} .

$\min \sum_{ij} (A_{ij} - \sum_{k=1}^n s_i x_i^{(k)} y_j^{(k)} B_{ij})^2.$ onde

s_{i}

$s_i$ são coeficientes reais positivos.

Isso é equivalente à decomposição de valor singular (SVD) quando $(B)_{ij} = 1$ .

Alguém sabe como esse problema é chamado? Existe um algoritmo conhecido como o SVD para a solução desse problema?

(migrado de math.SE)

linear-algebra matrix reference-request Memming
fonte

Eu acredito que este é SVD generalizado . A entrada da Wikipedia não é muito detalhada, então você provavelmente deve verificar as fontes vinculadas. Em particular, a página 466 deste link de livros do Google pode ser útil.

Ely

Para mim, isso não parece nada com o SVD generalizado. Especialmente porque B não é necessariamente diagonal ou simétrica, então cada ou pode aparecer muitas vezes na soma.

x

$x$

y

$y$

Victor Liu

B não precisa ser diagonal nem simétrica na SVD generalizada. Ambos os links que forneci indicam que A e B podem ser matrizes gerais de valor complexo das dimensões M-por-N e P-por-N, respectivamente.

Ely

Obrigado pela sugestão @EMS. Eu apreciaria se você puder elaborar a conexão.

Memming

Respostas:

Isso está longe de ser um SVD generalizado.

Se B é uma matriz positiva, você pode usar meu pacote BIRSVD http://www.mat.univie.ac.at/~neum/software/birsvd/

O artigo http://www.mat.univie.ac.at/~neum/software/birsvd/svd_incomplete_data.pdf, descrevendo o método, também fornece referências que você pode considerar fazer uma pesquisa bibliográfica.

Arnold Neumaier
fonte

Ah, transformando o problema em aproximação ponderada de baixa patente! Muito obrigado!

Memming

Para adicionar detalhes à resposta de @ Arnold, esse problema pode ser transformado em um problema de aproximação de baixa classificação ponderada, em que o objetivo é minimizar a norma ponderada em vez da norma de Frobenius. onde e denota o produto Schur (aka Produto Hadamard).

| | C - \sum s_{i} x_{i} y_{i}^{⊤} | |_{W}^{2}

$||C - \sum s_i \mathbf{x_i} \mathbf{y_i^\top}||^2_W$

| | C | |_{W} = | | C \circ W | |_{F}

$||C||_W = ||C \circ W||_F$

\circ

$\circ$

Memming 19/03/12

Sim. Isso dá um bom nome ao seu problema. Como resolvê-lo é uma questão diferente. Não é um problema padrão e foi bastante complicado encontrar um algoritmo que seja rápido e confiável.

Arnold Neumaier 19/03/12

@ArnoldNeumaier isso é ótimo, obrigado. seria possível obter uma licença e um aviso de direitos autorais com seu código? Como é agora, é um software proprietário. Se você o liberar sob a GPLv3 ou compatível, poderá encontrar o caminho para o pacote de álgebra linear do GNU Octave.

Juanpi