# Simultaneous Rank Minimization

Consider a rank minimization problem over two positive semi-definite matrices $X$ and $Y$ with $R = \operatorname{rank}(X) = \operatorname{rank}(Y)$: \begin{equation*} \begin{aligned} & \underset{X,Y}{\text{min}} & & R\\ &\text{subject to}& & \| X - \hat{X} \| \leq \epsilon_{1}\\ &&& \| Y - \hat{Y} \| \leq \epsilon_{2}\\ &&& X,Y \succeq 0 \\ &&& R = \operatorname{rank}(X) = \operatorname{rank}(Y)\\ \end{aligned} \end{equation*}

I could potentially solve (locally) the problem using a variant of the alternating projection method by simultaneously minimizing the rank of both matrices in each iteration.

Since both X and Y are PSD, I was curious if you could solve the problem using the trace (nuclear norm) heuristic, by encoding the problem in terms of, say, a linear combination of traces of PSD matrices $X$ and $Y$, subject to the above constraints. But that doesn't seem to guarantee the equality of ranks!

Any other approaches or insights into this problem or pointers is appreciated.

• There is nothing multi-objective here. You can just as well say that you want to minimize d under the constraint rank(X)=d and rank(Y)=d . – Johan Löfberg Sep 9 '15 at 18:39
• @JohanLöfberg Doesn't the problem amount to finding all the low-rank PSD matrices $X$ and $Y$ of the same rank that satisfy the above constraints? – Amir Sep 9 '15 at 20:12
• Now you are asking about something different. You are neither solving a multi-objective problem, nor are you looking for all solutions. You are looking for a pair X and Y having same and minimal rank satisfying the constraint. Standard optimization problem. – Johan Löfberg Sep 9 '15 at 20:53
• Indeed. You are absolutely right. I make the changes to the question. – Amir Sep 9 '15 at 22:36