# Questions tagged [matrix-completion]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
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 ...
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
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, ...
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)$?
• 103
1 vote
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$ ...
• 13.5k
1 vote
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)...
• 221
1 vote
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 ...
• 31
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 ...
• 3,641
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 ...
• 63
1 vote
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 ...