Questions tagged [matrix-completion]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
31 votes
3 answers

Quickly determining if a matrix has any PSD completion

Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion? Slightly more precisely: for simplicity let's assume ...
Paul Christiano's user avatar
4 votes
2 answers

Completing partial matrix to a positive definite matrix

Is the following problem known? Suppose one is given some of the entries of an $n \times n$ matrix $A$ over $\mathbb{R}$, so that the given entries are symmetric. Can one assign values to the ...
Lior Gishboliner's user avatar
1 vote
1 answer

Matrix Completion SDP Relaxation and Duality

I am studying the matrix Completion problem, as well as its SDP relaxation. However, I am having trouble deriving the final SDP form of the matrix completion problem. I will give some background, ...
alternate direction's user avatar
2 votes
2 answers

How to determine the range of values ​of A(i,j) in Covariance matrix A?

Let $A(i,j), i,j=0,1,2$ be the covariance matrix of three random variables. If we know all the entries except $A(2,0)$ and $A(0,2)$, how to determine the range of possible values of $A(2,0)$?
phybrain's user avatar
  • 103
1 vote
0 answers

Matrix completion in $2\times2$ case by nuclear norm minimization to guarantee rank $1$?

Does fixing diagonal entries and minimizing nuclear norm under weighted sum of entries conditions produce a rank $1$ matrix? I think the answer for this is no. At least could it be true in $2\times2$ ...
Turbo's user avatar
  • 13.5k
1 vote
0 answers

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 \forall (i,j)...
felasfaw's user avatar
  • 221
1 vote
0 answers

Keshavan-Montanari-Oh matrix completion — clearing step

I am trying to implement the algorithm for matrix completion proposed by Keshavan, Montanari and Oh (2009). It consists of three steps: Trimming which nulls some rows and columns to make the high ...
J. Doe's user avatar
  • 31
17 votes
1 answer

A matrix completion problem

In their paper, Corners of normal matrices, Rajendra Bhatia and Man-Duen Choi asked the following question: Given a matrix pair $(B,C)$ where $B,C∈M_n$, does there exist matrices $A,D ∈ M_n$ such ...
Mustafa Said's user avatar
  • 3,641
6 votes
1 answer

SDP formulation of noisy low-rank matrix completion

Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...
tngo's user avatar
  • 63
1 vote
0 answers

Nonunique low-rank matrix completion from a few entries

Suppose we want to have a good approximation for the following NP-hard problem $$\min_{\bf X} \operatorname{rank}({\bf X}) \text{ s.t. } \mathcal{A}({\bf X}) = {\bf b}, {\bf X} \succeq 0$$ where ${\bf ...
Anadim's user avatar
  • 439