# Questions tagged [matrix-completion]

The matrix-completion tag has no usage guidance.

10
questions

31
votes

3
answers

3k
views

### 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 ...

4
votes

2
answers

367
views

### 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 ...

1
vote

1
answer

1k
views

### 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, ...

2
votes

2
answers

294
views

### 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)$?

1
vote

0
answers

123
views

### 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$ ...

1
vote

0
answers

454
views

### 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)...

1
vote

0
answers

83
views

### 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 ...

17
votes

1
answer

705
views

### 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 ...

6
votes

1
answer

2k
views

### 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 ...

1
vote

0
answers

217
views

### 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 ...