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.

  • 3
    $\begingroup$ 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 . $\endgroup$ – Johan Löfberg Sep 9 '15 at 18:39
  • $\begingroup$ @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? $\endgroup$ – Amir Sep 9 '15 at 20:12
  • $\begingroup$ 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. $\endgroup$ – Johan Löfberg Sep 9 '15 at 20:53
  • $\begingroup$ Indeed. You are absolutely right. I make the changes to the question. $\endgroup$ – Amir Sep 9 '15 at 22:36

Your Answer

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

Browse other questions tagged or ask your own question.