Skip to main content

The nuclear normnuclear 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 (i,j)\in \Omega \end{align} where

\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  (seee.g., see Theorem 1.1 of Candes and Recht, 2008 paper    ).

Let the underlying matrix $M$ be semi positive definitesemidefinite.

  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.

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 (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(see Theorem 1.1 of Candes and Recht, 2008 paper    )

Let the underlying matrix $M$ be semi positive definite.

  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

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.

Source Link
felasfaw
  • 221
  • 1
  • 8

psd condition for matrix completion

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 (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(see Theorem 1.1 of Candes and Recht, 2008 paper )

Let the underlying matrix $M$ be semi positive definite.

  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