Otimização com restrições ortogonais

Estou trabalhando em visão computacional e preciso otimizar uma função objetiva que envolve a matriz e a matriz é uma matriz ortogonal. $X$ $X$

m a x i m i z e f (X)

$maximize \ \ f(X)$

s . t X^{T} X = I

$s.t \ \ X^T X=I$ Onde é a matriz da unidade. Estou lendo alguns artigos e eles falavam de terminologia complicada, como otimização sobre a variedade grassmaniana, variedade Stiefel. Basicamente, o gradiente nessas variedades será diferente dos gradientes regulares nos espaços euclidianos.

I

$I$

Você pode sugerir um artigo fácil de ler para que eu possa implementar o método baseado em gradiente nessas variedades. Se houver exemplos simples do Matlab que ilustrem os documentos, serão úteis

obrigado

optimization orthogonal Lan Trần Thị
fonte

Você pode fornecer mais informações sobre o seu problema em questão? Tal como está, é muito amplo responder. Por exemplo, você pode muito bem gerar uma matriz quadrada aleatória , obter o seu SVD tal que e usar como uma solução candidato para .

Y

$Y$

Y = U S V^{T}

$Y= USV^T$

U

$U$

X

$X$

usεr11852

O que é ?

f (.)

$f(.)$

User603

Você realmente precisa do tratamento geral dos coletores Stiefel ou seria suficiente ter informações sobre a restrição (muito mais simples) ? No último caso, o problema se reduz a mover-se ao longo de círculos. O exemplo mais simples disso é em duas dimensões, nas quais a restrição define o círculo unitário: o gradiente em um ponto é direcionado ao longo da linha tangente naquele ponto, mas, para seguir o gradiente, é necessário mover-se ao longo do círculo e não na linha tangente . Essa ideia generaliza. (cc @ usεr11852)

X^{'} X = I

$X^\prime X=I$

whuber

@ whuber: +1 e obrigado por me cc :: ing. Eu obviamente concordo. Com o meu exemplo, eu só queria mostrar que mesmo uma pesquisa aleatória simplista seria suficiente para fornecer soluções candidatas válidas.

usεr11852

@ GeoMatt Isso pode ser mais elementar do que você pensa. A distinção é esta: no plano, é uma função definida no círculo unitário . Você pode otimizá-lo estendendo-o para uma função de todos em uma vizinhança do círculo unitário e usando multiplicadores Lagrange para impor a restrição . Ou, você pode parametrizar o círculo unitário como , tornando uma função periódica da variável e otimizá-lo sem restrições. Exatamente o mesmo método funciona com matrizes ortogonais (e variedades Grassmann).

f

$f$

x^{2} + y^{2} = 1

$x^2+y^2=1$

(x, y)

$(x,y)$

x^{2} + y^{2} = 1

$x^2+y^2=1$

(x, y) = (\cos (t), \sin (t))

$(x,y)=(\cos(t),\sin(t))$

f

$f$

t

$t$

whuber

Respostas:

Eu achei o seguinte artigo útil:

Edelman, A., Arias, TA e Smith, ST (1998). A geometria de algoritmos com restrições de ortogonalidade . Revista SIAM sobre Análise e Aplicações de Matrizes, 20 (2), 303-353.

Este documento tem muito mais informações do que você pode precisar, em termos de geometria diferencial e métodos de otimização de ordem superior.

No entanto, as informações para responder à sua pergunta são realmente bastante diretas e, de fato, estão contidas principalmente nas equações 2.53 e 2.70, que são da forma onde o gradiente nominal é corrigida para constrangido gradiente subtraindo-se fora a sua projecção para a solução actual . Este é o normal para o coletor, semelhante ao movimento circular , e garante que o gradiente corrigido seja tangente ao coletor.

\nabla f = G - X Φ

$\nabla{f}=G-X\Phi$

G = \frac{\partial f}{\partial X}

$G=\frac{\partial{f}}{\partial{X}}$

\nabla f

$\nabla{f}$

Φ

$\Phi$

X

$X$

Nota: Estas fórmulas supor que você já está no colector, ou seja, . Portanto, na prática, você precisará garantir que sua condição inicial seja apropriada (por exemplo, , possível retangular). Você também pode precisar ocasionalmente corrigir erros de arredondamento e / ou truncamento acumulados (por exemplo, via SVD, consulte o exemplo "ZCA" abaixo). $X^TX=I$ $X_0=I$

No caso sem restrições, , enquanto no caso restrito, assume duas formas: que corresponde ao "coletor Grassmann". A distinção aqui é que é insensível às rotações , uma vez que para uma rotação e , temos . $\Phi=0$ $\Phi$

Φ_{G} = X^{T} G ⟹ \nabla_{G} f = (I - X X^{T}) G

$\Phi_{\mathrm{\small{G}}}=X^TG\implies\nabla_{\mathrm{\small{G}}}{f}=\left(I-XX^T\right)G$

\nabla_{G}

$\nabla_{\mathrm{\small{G}}}$

Q^{T} Q = I

$Q^TQ=I$

X = X_{0} Q

$X=X_0Q$

X X^{T} = X_{0} X_{0}^{T}

$XX^T=X_0X_0^T$

A segunda forma é que corresponde ao " Stiefel manifold ", e é sensível a rotações.

Φ_{S} = G^{T} X ⟹ \nabla_{S} f = G - X G^{T} X

$\Phi_{\mathrm{\small{S}}}=G^TX\implies\nabla_{\mathrm{\small{S}}}{f}=G-XG^TX$

Um exemplo simples é a aproximação de uma determinada matriz com por uma matriz ortogonal , minimizando o erro dos mínimos quadrados. Nesse caso, temos O caso irrestrito tem a solução , porque não estamos preocupados em garantir que seja ortogonal. $A\in\mathbb{R}^{n\times{p}}$ $p\leq{n}$ $X$

f [X] = \frac{1}{2} ‖ X - A ‖_{F}^{2} = \frac{1}{2} \sum_{i j} {(X_{i j} - A_{i j})}^{2} ⟹ G = X - A

$f[X]=\tfrac{1}{2}\|X-A\|_F^2=\tfrac{1}{2}\sum_{ij}\left(X_{ij}-A_{ij}\right)^2\implies{G}=X-A$

\nabla f = G

$\nabla{f}=G$

X = A

$X=A$

X

$X$

Para o caso Grassmann, temos Isso só pode ter uma solução: é quadrado, em vez de "fino" , porque se , terá um espaço nulo .

\nabla_{G} f = (X X^{T} - I) A = 0

$\nabla_{\mathrm{\small{G}}}{f}=\left(XX^T-I\right)A=0$

A

$A$

p < n

$p<n$

X

$X$

Para o caso Stiefel, temos que pode ser resolvido mesmo quando .

\nabla_{S} f = X A^{T} X - A = 0

$\nabla_{\mathrm{\small{S}}}{f}=XA^TX-A=0$

p < n

$p<n$

Esses dois casos, Grassmann vs. Stiefel, correspondem essencialmente à diferença entre " PCA vs. ZCA whitening ". Em termos de SVD , se a matriz de entrada for , então as soluções serão e . A solução PCA se aplica apenas a uma entrada quadrada, ou seja, deve ser a " matriz de covariância ". No entanto, a solução ZCA pode ser usada quando é uma " matriz de dados ". (Isso é mais conhecido como o problema de procrustações ortogonais .) $A=USV^T$ $X_{\mathrm{\small{G}}}=U$ $X_{\mathrm{\small{S}}}=UV^T$ $X_{\mathrm{\small{G}}}$ $A$ $X_{\mathrm{\small{S}}}$ $A$

GeoMatt22
fonte

Eu não acho que é um bom ponto de partida, porque então a derivada é 0.

X_{0} = I

$X_0=I$

user103828