1
$\begingroup$

The nuclear norm minimization for the matrix completion problem is given by

\begin{align} \textrm{minimize } \quad &\|X\|_{*}\\ \textrm{subject to } \quad & X_{ij}=M_{ij} \quad \forall (i,j)\in \Omega \end{align}

where $\Omega$ is the set of randomly sampled entries. There are results that show that one can recover the underlying matrix $M$ with high probability given "enough" measurements (e.g., see Theorem 1.1 of Candes and Recht, 2008 paper).

Let the underlying matrix $M$ be positive semidefinite.

  1. Without putting any condition on the optimization problem, simply considering the minimization problem above, is it expected that one would recover a positive definite matrix?

  2. If the question for $(1)$ is negative, are there recent results that show the positive definite completion and characterize the number of samples, successful recovery rate,...

Thank you for hints, directions or suggestions.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ $\mathrm X$ does not even need to be square, does it? I suspect you are interested in the positive semidefinite matrix completion problem. You may want to take a look at Monique Laurent's papers on that. Here's one of them: Complexity of the positive semidefinite matrix completion problem with a rank constraint $\endgroup$
    – Rodrigo de Azevedo
    Commented Oct 28, 2016 at 12:24
  • 1
    $\begingroup$ If $\mathrm X$ is square, symmetric and PSD, then minimizing the nuclear norm is equivalent to minimizing the trace. Take a look at Emmanuel Candès's talk. $\endgroup$
    – Rodrigo de Azevedo
    Commented Oct 28, 2016 at 12:31
  • $\begingroup$ Dear Rodrigo, thank you for the links esp. the talk by Candes. I appreciate it. $\endgroup$
    – felasfaw
    Commented Oct 31, 2016 at 17:35
  • $\begingroup$ You might consider adding a top-level tag in order to make more people see this question. $\endgroup$
    – Stefan Kohl ♦
    Commented May 8, 2017 at 9:33

0

Reset to default

You must log in to answer this question.