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 ...
- 747
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 ...
- 418
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)$?
- 103
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$ ...
- 13.5k
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)...
- 221
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 ...
- 31
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 ...
- 3,641
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 ...
- 63
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 ...
- 439