Cómo aprender una matriz de Vandermonde a partir de datos

Question

_{Publicado de forma cruzada en <a href="https://or.stackexchange.com/questions/7391/estimation-of-vandermonde-matrix">Investigación de operaciones SE </a>.}

---

Me gustaría discutir cómo abordar un problema de optimización para aprender un Matriz de Vandermonde . En particular, tengo un problema de optimización de la siguiente forma:

\begin{align} V &= \operatorname{argmin}_{V}\|A - \operatorname{diag}(Vb )C\|_F^2 \end{align} donde $A,C$ son $N \times N$ matrices, $V$ es un $N \times K$ Matriz de Vandermonde con $N >K$ y $b$ es un $K \times 1$ vector de coeficientes.

Se trata de una generalización del diseño de filtros FIR, donde en lugar de encontrar los coeficientes del filtro $b$ buscamos los vectores base $\{v_1, \ldots, v_k\}$ de la matriz de Vandermonde. Cada uno de estos vectores es tal que $v_{i+1}= v_i \odot v_1 $ es decir, es una progresión geométrica sobre las filas.

¿Cómo puedo aprender la matriz $V$ ? ¿Existe una forma de reescribir este problema en una forma más fácil de optimizar?

El problema no es convexo, ya que es la composición de una norma con un mapeo no afín de la $N$ las variables contenidas en $v_1$ . Aprovechando la relación entre la norma de Frobenius y la propiedad de traza, pude llegar al problema de minimizar $V$ sobre la función:

$$\operatorname{vec}(Z)^\top \operatorname{vec}(Z) -2 \operatorname{vec}(A)^{\top}\operatorname{vec}(Z) $$

donde $\operatorname{vec}(Z)= \operatorname{vec}(C)^\top (I \odot I) \operatorname{vec}(Vb)$ . ¿Podría esto ayudar a resolver para $V$ ? (o mejor, para $v_1$ ?).

Answer 1

$ \def\bbR#1{{\mathbb R}^{#1}} \def\h#1{{\odot #1}} \def\a{\alpha}\def\b{\beta}\def\e{\varepsilon} \def\o{{\tt1}}\def\p{\partial} \def\B{\Big}\def\L{\left}\def\R{\right} \def\LR#1{\L(#1\R)} \def\BR#1{\B(#1\B)} \def\bR#1{\big(#1\big)} \def\vecc#1{\operatorname{vec}\LR{#1}} \def\diag#1{\operatorname{diag}\LR{#1}} \def\Diag#1{\operatorname{Diag}\LR{#1}} \def\SDiag#1{\operatorname{SubDiag}\LR{#1}} \def\trace#1{\operatorname{Tr}\LR{#1}} \def\qiq{\quad\implies\quad} \def\grad#1#2{\frac{\p #1}{\p #2}} \def\c#1{\color{red}{#1}} \def\m#1{\left[\begin{array}{r}#1\end{array}\right]} $ Construir una matriz de Vandermonde $V$ de la independiente vectorial $x$ como sigue $$\eqalign{ V &= \m{x^\h{0}&x^\h{\o}&x^\h{2}&x^{\odot 3}&\ldots&x^\h{(k-1)}} \;\in\bbR{n\times k} \\ &= \m{\o&&x&&x^\h{2}&x^\h{3}&\ldots&x^\h{(k-1)}} \\ \\ x^{\odot 3} &= x\odot x\odot x \quad\quad\bR{{\rm Hadamard\;powers/products}} \\ dx^{\odot 3} &= \c{dx}\odot x\odot x + x\odot \c{dx}\odot x + x\odot x\odot \c{dx} \\ &= 3x^\h{2}\odot {dx} \\ }$$ El diferencial de la matriz (wrt $x$ ) se puede calcular como $$\eqalign{ dV &= \m{0&&\o&&2x^{\odot\o}&&3x^{\odot2}&\ldots} \odot \m{dx&dx&dx&\ldots} \\ &= \bR{VD_k^T}\odot\bR{dx\,\o^T} \\ &= \Diag{dx}\cdot \bR{VD_k^T} \\ D_k &= \SDiag{1,2,3,\ldots} = \m{ 0 & 0 & 0 & \ldots & 0 \\ \c{\o} & 0 & 0 & \ldots & 0 \\ 0 & \c{2} & 0 & \ldots & 0 \\ 0 & 0 & \c{3} & \ldots & 0 \\ \vdots & \vdots & \vdots &\ddots \\ } \;\in\bbR{k\times k} \\ }$$ El $D_k$ es la matriz Matriz de diferenciación para el espacio polinómico.

Para facilitar la escritura, defina las variables de la matriz $$\eqalign{ M &= {\Diag{Vb}C-A} \\ H &= \diag{MC^T}\,b^T \\ }$$ Tenga en cuenta que $H$ es una función de $M$ que es una función de $V$ que es una función de $x$ .
Por lo tanto, todo $\big($ excepto en el caso de $A,b,C,D_k\big)$ es una función polinómica de $x$ .

Ahora escribe la función de coste y calcula su diferencial y el gradiente con respecto a $x$ . $$\eqalign{ \phi &= \frac 12 M:M \\ d\phi &= M:dM \\ &= M:\BR{\Diag{dV\,b}\,C} \\ &= H:dV \\ &= H:\LR{\Diag{dx}\cdot \bR{VD_k^T}} \\ &= \LR{HD_k V^T}:\Diag{dx} \\ &= \diag{HD_k V^T}:dx \\ \grad{\phi}{x} &= \diag{HD_k V^T} \\ }$$ donde los dos puntos denotan el producto de Frobenius, que es una notación concisa notación para la traza $$\eqalign{ A:B &= \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij} \;=\; \trace{A^TB} \\ A:A &= \big\|A\big\|^2_F \\ }$$ Las propiedades de la función de rastreo subyacente permiten que los términos de un producto de Frobenius se puedan reordenar de muchas maneras diferentes, por ejemplo $$\eqalign{ A:B &= B:A \\ A:B &= A^T:B^T \\ C:AB &= CB^T:A = A^TC:B \\ \\ }$$

---

Al poner el gradiente a cero se obtiene un complicado sistema de ecuaciones polinómicas (no lineales) $$\eqalign{ f(x) = 0 \;\in\bbR{n} }$$ cuyas raíces hay que encontrar. Una vez que el óptimo $x$ ha sido localizado, el correspondiente $V$ se puede construir una matriz, como se muestra en la parte superior del post.

Sin duda, habrá muchas, muchas raíces de $f(x),\,$ todos los cuales son local extremos de la función de costes. Cada uno de ellos debe ser comprobado para determinar si es el deseado global mínimo.

Tal vez usando un sistema de álgebra computacional se puedan encontrar las raíces usando una base de Gröbner o algo así.

Answer 2

Sugerencia : Tal vez pueda ayudar a considerar $$\left[\begin{array}{lllll}1&0&0&0&0\\x&0&0&0&0\\0&x&0&0&0\\0&0&x&0&0\\0&0&0&x&0\end{array}\right]^4 = \left[\begin{array}{lllll}1&0&0&0&0\\x&0&0&0&0\\x^2&0&0&0&0\\x^3&0&0&0&0\\x^4&0&0&0&0\end{array}\right]$$

Junto con la regularización resolver una matriz con productos de Kronecker y algún enfoque iterativo / continuidad.