Otimização com restrições ortogonais

8

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

maximize  f(X)

s.t  XTX=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

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

Lan Trần Thị
fonte
11
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 . YY=USVTUX
usεr11852
11
O que é ? f(.)
User603
4
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)XX=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
4
@ 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). fx2+y2=1(x,y)x2+y2=1(x,y)=(cos(t),sin(t))ft
whuber

Respostas:

7

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.

f=GXΦ
G=fX
fΦ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).XTX=IX0=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 .Φ=0Φ

ΦG=XTGGf=(IXXT)G
GQTQ=IX=X0QXXT=X0X0T

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

ΦS=GTXSf=GXGTX

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.ARn×ppnX

f[X]=12XAF2=12ij(XijAij)2G=XA
f=GX=AX

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

Gf=(XXTI)A=0
Ap<nX

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

Sf=XATXA=0
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=USVTXG=UXS=UVTXGAXSA

GeoMatt22
fonte
2
Eu não acho que é um bom ponto de partida, porque então a derivada é 0.X0=I
user103828