# Generate approximately semi-orthogonal tall matrix approximately satisfying constraints

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.

• $S > m$, right? – Rodrigo de Azevedo Jul 1 '18 at 17:46
• @RodrigodeAzevedo Both $S$ and $m$ are independently controlled parameters, so either could be larger than the other. – user3658307 Jul 1 '18 at 23:55
• Let $S = 2$ and $m =3$. How can one have $3$ orthonormal vectors in $2$-dimensional space? – Rodrigo de Azevedo Jul 2 '18 at 0:08
• @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). – user3658307 Jul 2 '18 at 4:55
• 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. – loup blanc Jul 12 '18 at 9:18

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.

• Take a look at this numerical experiment. – Rodrigo de Azevedo Jul 4 '18 at 21:02
• 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! :) – user3658307 Jul 4 '18 at 21:12
• 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. – Rodrigo de Azevedo Jul 4 '18 at 21:34