5
$\begingroup$

I have a set of matrices $\{(A_i,D_i)\}$ for $i\in\{1,\ldots,n\}$, where:

  • Each $D_j\in\mathbb{R}^{S\times S}$ is diagonal, and every entry on the main diagonal is non-negative.

  • Each $A_j\in\mathbb{R}^{m\times m}$ is symmetric and positive definite, with every entry being non-negative.

I want to find a matrix $B\in\mathbb{R}^{m\times S}$ such that: $$ A_i \approx B D_i B^T \;\;\;\forall\;\;\;1\leq i \leq n \\ B^TB\approx I $$ However, everything is noisy (meaning $A_i$ and $D_i$ always have some random perturbation). This means (I assume) that I need something like: $$ B^* = \arg\min_B \;\alpha||B^TB - I|| + \beta\sum_{i=1}^n || A_i - BD_iB^T|| $$ for some matrix norm (e.g. Frobenius) and (hyper-)parameters $\alpha,\beta\in\mathbb{R}$. I am not too picky about the exact formulation, however, so feel free to tweak it. For instance, perhaps there is a way to make the orthogonality a hard constraint.

My question: how do I solve an optimization problem like the one above?

What have I tried: well, this reminds me of an eigenvalue decomposition problem (if $n=1$ especially), but I have a set of problems I'd like to simultaneously satisfy. One odd thing though is that the $D_j$ are known, or at least estimated (albeit with noise). My first thought was to rearrange this into a linear system somehow, but I have not been able to do so (so far).

If there is some literature I can look into relating to this problem, that would be a more than good enough answer. My apologies for the lack of optimization/numerical linear algebra knowledge.

Note: I have already tried to post this on math stack exchange, but to no avail.

Improve this question
$\endgroup$
5
  • $\begingroup$ $S > m$, right? $\endgroup$
    – Rodrigo de Azevedo
    Jul 1, 2018 at 17:46
  • $\begingroup$ @RodrigodeAzevedo Both $S$ and $m$ are independently controlled parameters, so either could be larger than the other. $\endgroup$
    – user3658307
    Jul 1, 2018 at 23:55
  • $\begingroup$ Let $S = 2$ and $m =3$. How can one have $3$ orthonormal vectors in $2$-dimensional space? $\endgroup$
    – Rodrigo de Azevedo
    Jul 2, 2018 at 0:08
  • $\begingroup$ @RodrigodeAzevedo Thanks for the comment. It makes sense (and it also made me realize I had mistyped the shape of $B$). We can assume $m > S$ (note that I've edited the question so their roles are reversed now). $\endgroup$
    – user3658307
    Jul 2, 2018 at 4:55
  • $\begingroup$ I think you have not thought for more than 1 minute about the question you are asking. In fact, that you write is non-sense except if $S=m$. Indeed, $B^TB≈I$ implies that $B^TB$ is invertible and $S≤m$. $Ai≈BD_iB^T$ and $A_i>0$ imply that $BD_iB^T$ is invertible and $m≤S$. On the other hand, your formulae imply that $A_iA_j≈A_jA_i$, what you need to add in the above assumptions. $\endgroup$
    – loup blanc
    Jul 12, 2018 at 9:18

1 Answer 1

Reset to default
2
$\begingroup$

Let us consider the simplest case, i.e., the case where $n = 1$. Rephrasing slightly:

Given

  • symmetric and positive definite matrix $\mathrm A \in \mathbb R^{m \times m}$

  • positive semidefinite diagonal matrix $\mathrm D \in \mathbb R^{p \times p}$

find a tall matrix $\mathrm X \in \mathbb R^{m \times p}$ with orthonormal columns such that $\rm A \approx X D X^\top$, or, $\rm A X \approx X D$.

Using the spectral norm, we have the following non-convex optimization problem in $\mathrm X \in \mathbb R^{m \times p}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm X - \mathrm X \mathrm D \|_2\\ \text{subject to} & \mathrm X^\top \mathrm X = \mathrm I_p\end{array}$$

The feasible region, defined by $\mathrm X^\top \mathrm X = \mathrm I_p$, is a Stiefel manifold, whose convex hull is defined by $\mathrm X^\top \mathrm X \preceq \mathrm I_p$, or, equivalently, by the inequality $\| \mathrm X \|_2 \leq 1$. Therefore, a convex relaxation of the original optimization problem is

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm X - \mathrm X \mathrm D \|_2\\ \text{subject to} & \| \mathrm X \|_2 \leq 1\end{array}$$

Let $\rm {\bar X}$ denote the solution of the relaxed problem. If $\rm {\bar X}^\top \rm {\bar X} \approx \mathrm I_p$ and $\rm A {\bar X} \approx \rm {\bar X} D$, then we may have something we could call a solution of the original problem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Take a look at this numerical experiment. $\endgroup$
    – Rodrigo de Azevedo
    Jul 4, 2018 at 21:02
  • $\begingroup$ Very cool; thank you so much! Some minor questions, if you don't mind. (1) For $n>1$, if one optimizes over $\sum_i ||A_i X-XD_i||_2 $, is this still a good relaxation? Convex sums being convex, it seems reasonable to me. (2) Is there a good tutorial/article/book you can recommend for this area? Apologies for the lack of knowledge. Also, thanks for the link to the cvxpy code! :) $\endgroup$
    – user3658307
    Jul 4, 2018 at 21:12
  • $\begingroup$ Try the Frobenius norm in the objective function, too. (1) I don't know. I would just try a few numerical experiments. In my first comment, I posted a link to a numerical experiment in which the Frobenius norm sort of worked, and the taller the matrix, the better it seemed to work. (2) I never read any tutorials or articles on this. I just found a post on Math Stack Exchange on the convex hull of the Stiefel manifold and I decided to try some numerical experiments using CVXPY. $\endgroup$
    – Rodrigo de Azevedo
    Jul 4, 2018 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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