0
$\begingroup$

Problem description

Given data at many time instance $t$,

$$\min _{\alpha, \xi, \beta} \lVert y(t) - \alpha e^{\Lambda t} \beta \rVert_F$$ with $$ \lVert \alpha \rVert_F^2 = 1 $$

where $y(t) \in \mathbb{R}^{n \times M}$, $\Lambda \in \mathbb{R}^{r\times r}$ is a diagonal matrix, $\alpha \in \mathbb{R}^{n \times r}$, $\beta \in \mathbb{R}^{r \times M}$

Special case

if $\alpha = I$, the problem becomes a classical problem in variable projection for nonlinear least square, which has been studied for decades.

The benefit of $\alpha = I$ is that, the nonlinear and linear part becomes separable through pseudo-inverse.

What I currently do

I can simply (blindly) use an optimization package to generally solve this problem by do naive gradient descent, it looks like a neural network training process, without leveraging the structure of the problem.

It works for toy problem, like when n,r less than 3.

The downside is that, since it doesn't assume any structure to leverage, the computational time is costly.

What I want to know

I want to know if any one know which category does this problem belongs to, and if there is better algorithm existing to solve this.

$\endgroup$
  • $\begingroup$ A small question - the symbol $\|\alpha\|_2^F$ is the operator norm w.r.t the spectral norm in the domain and the Frobenius norm in the range? $\endgroup$ – Alex Shtof May 22 '18 at 8:31
  • $\begingroup$ @Alex I am sorry. It should be $$\lVert \alpha \rVert_F^2 = 1$$ $\endgroup$ – ArtificiallyIntelligence May 22 '18 at 13:50
1
$\begingroup$

First, note that the problem is non-convex, and I am not aware of a convex reformulation. That is, we resort to methods which might get stuck in a non-optimal point instead of converging to the optimum, including the naive gradient descent.

The first thing I would try is alternating minimization. Note that the Frobenius norm is the Euclidean norm of the vector of stacked matrix columns. Thus, everything can be expressed in terms of vectors.

When $\alpha$ is kept constant - we get a linear least squares problem, which is easy. When $\beta$ is kept constant, we get a GTRS (Generalized Trust-Region Subproblem) with interval inequality, which also has known global solution algorithms. Thus is one way to exploit problem structure.

Next thing I would try would be a proximal variant of the above.

Good luck!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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