I have a question.

Suppose we want to solve an optimization problem:

Consider $S \in \mathbb{R}^{N \times T}, T >> S$

$$\min_{S} f(S) \mbox{ s.t. } SS^T \mbox{is diagonal}$$

Which means each rows of the matrix $S$ is mutually orthogonal.

I am suggested to solve this alternative problem by the following method:

$$\min_{S} f(S) + \|\mathcal{P}(SS^T)\|_1$$, in which $\mathcal{P}$ is a projection onto the off-diagonal indexes.

But I don't think this $\ell_1$ penalty will promote the orthogonality between each rows by simply promote the sparsity of the off diagonal elements, since we are not doing any actions like block coordinate descent to promote the orthogonality.

Any suggestions?

  • $\begingroup$ Hi: Clearly, if each diagonal element of the matrix is zero and no other elements are zero, then the columns of the matrix define a basis which is orthogonal. The part I don't get is why minimizing the norm of the projection results in those zeros. $\endgroup$
    – mark leeds
    Dec 21 '18 at 13:12
  • $\begingroup$ @markleeds. I think you mean the row of the matrix $S$ define a basis which is orthogonal? $\endgroup$
    – Z-Harlpet
    Dec 21 '18 at 23:03
  • $\begingroup$ You are correct. My mistake and thanks.. Also, if you have any ideas on the confusion I have, it's appreciated. $\endgroup$
    – mark leeds
    Dec 22 '18 at 5:18
  • $\begingroup$ Oh God. It is so much better than the Math StackExchange. You guys are so welcome. $\endgroup$
    – Z-Harlpet
    Dec 22 '18 at 5:56

First, a warm welcome to StackExchange! Consider this as a bit of brainstorming.

Given that the diagonal elements are positive, I think there is a particular geometry of your parameters: They live in the Generalized Stiefel Manifold, where each point is a scaled orthonormal frame of dimension $T$ embedded in $\mathbb{R}^N$.

Let me rewrite : $$ \begin{align*} SS^\top &= \Lambda\\ \frac{1}{\sqrt{\Lambda}}SS^\top\frac{1}{\sqrt{\Lambda}^\top} &= \frac{1}{\sqrt{\Lambda}}\Lambda\frac{1}{\sqrt{\Lambda}^\top}\\ B SS^\top B^\top &= B\Lambda B^\top\\ OO^\top &= I \end{align*} $$ where $\Lambda$ is the $N\times N$ diagonal matrix, $B=\frac{1}{\sqrt{\Lambda}}\succ0$ and $O=BS$. Similarly, $S=\sqrt{\Lambda}O$. Division and square roots are element-wise. Now $O$ lives on the usual Stiefel manifold. When $B$ is known, the problem can simply be solved by a Riemannian optimization on the Generalized Stiefel Manifold (see manopt). However, now, this is not the case.

So let's take a second look at the problem at hand: $$\min_{S} f(S) \mbox{ s.t. } SS^T \mbox{is diagonal}$$

This can be formulated in terms of the new variables: $$\min_{\Lambda,O} f(\sqrt{\Lambda}O) \mbox{ s.t. } OO^T =I \,\wedge\, \Lambda>0$$

where $O$ is Stiefel, and $\Lambda>0$. The latter can also be denoted by a vector $\mathbf{\lambda}\equiv \text{diag}(\Lambda)$ and $\lambda>0$. The true exponential and logarithm maps for the Stiefel manifold are available (for instance in Manopt) and $\lambda$ has a simpler constraint (for projection). So from this point on, I am being more heuristic and would suggest to alternatively optimize these two:

  1. Fix $\lambda$, optimize $O$ on the Stiefel manifold using the chain rule: $$ \nabla_O f(\sqrt{\Lambda}O) = \sqrt{\Lambda} \nabla_{S} f(S) $$
  2. Fix $O$, optimize for $\sqrt{\lambda}$ (can also use positivity constraint): $$ \nabla_{\sqrt{\Lambda}} f(\sqrt{\Lambda}O) = O \nabla_{S} f(S) $$

You can of course use gradient descent but also other sophisticate algorithms like Riemannian-LBFGS / trust-region.

  • $\begingroup$ You're brain flies in a different air-zone than mine ( higher ) but, just out of curiosity, what topic does what you wrote about fall under ? Advanced optimization theory or mathematical programming or convex optimization rtc ? I looked at the link and will never understand it but rather just curious because I am somewhat familiar with more basic optimization theory. Thanks. $\endgroup$
    – mark leeds
    Dec 22 '18 at 5:24
  • $\begingroup$ Hi, Thank you so much for your answer. And we can see that the problem is highly nonconvex. $\endgroup$
    – Z-Harlpet
    Dec 22 '18 at 6:41
  • $\begingroup$ @markleeds, It is just a topic in matrix optimization on manifold. You can read Absil's book for more details. $\endgroup$
    – Z-Harlpet
    Dec 22 '18 at 22:39
  • $\begingroup$ Thanks Z-Harlpet. Maybe I'll check it out someday but manifolds are not my thing. $\endgroup$
    – mark leeds
    Dec 23 '18 at 1:18
  • $\begingroup$ Z-Harlpet: I looked for the book for the heck of it and, at a glance, it seems way more readable than the link that Tolga sent.. I'm saving the pdf and will hopefully get the time to check it out someday. Thanks a lot and all the best. $\endgroup$
    – mark leeds
    Dec 23 '18 at 1:30

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.