Questions tagged [matrix-completion]

Matrix completion is the task of filling in the missing entries of a partially observed matrix.

14 questions
41 views

Completion of partial latin squares

I'm reading a PDF about completing partial latin squares. The reference is https://ajc.maths.uq.edu.au/pdf/22/ocr-ajc-v22-p247.pdf There is a fact that doesn't have a proof here, and I can't find it: ...
58 views

Finding matrix with lowest possible rank

Find the values of $x$ for which the matrix \begin{bmatrix} x & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & x \\ \end{bmatrix} has the lowest rank. Since ...
49 views

How do I complete a matrix so that its columns are orthogonal?

I'm not sure how to start on these types of problems. I know that the dot product of the columns have to be zero between each pair. Do I set up a system of linear equations for this? If so, what ...
15 views

I'm trying to understand the exact degrees of freedom involved in constructing Hadamard matrices with elements in $\{1, -1\}$, and if possible, reduce them in such a way that they can be ...
106 views

“Shadow prices” interpretation of the dual certificate of nuclear norm optimization

In nuclear norm based matrix completion, there exists a low rank matrix $M$ of which only the indicies in $\Omega$ are sampled. Candes and Recht (2008) recover the original matrix using following ...
36 views

Approximate Isometry in Matrix Completion

I am working through the Recht (2011) paper titled, "A Simpler Approach to Matrix Completion", and there is one step on page 3422 (10 in the document) I am really struggling to understand: We show ...
540 views

When is the Frobenius norm bounded by the nuclear norm?

I am reading the Recht (2011) paper titled, "A Simpler Approach to Matrix Completion", and I cannot figure out the last inequality of the last line on page 3422 (page 10 of the document). The ...
71 views

Low-rank matrix satisfying linear constraints linear mapping

Let $X \in \mathbb{R}^{m \times n}$ be a matrix that is assumed to be low rank. According to, Recht, Benjamin; Fazel, Maryam; Parrilo, Pablo A., Guaranteed minimum-rank solutions of linear matrix ...
85 views

Proof that nuclear norm minimization gives a unique solution

I am reading a paper "A simpler approach to matrix completion" Which talks about matrix completion using nuclear norm minimization. In section 4 it proofs that, the optimization problem gives a ...
26 views

Given a matrix $M \in \mathbb{R^{m \times n}}$ whose some entries in $\Omega$ are missing, I'm interested in filling in the matrix (Matrix Completion). I know a natural approach is to seek the lowest ...
749 views

How to convert the matrix completion problem to the standard SDP form?

Given the matrix completion problem defined below. \begin{equation} \begin{array}{ll} \text{minimize }{X \in \mathbb{R}^{m \times n}} & \sum_{(i,j) \in \Omega} ( X_{ij} - Z_{ij} )^2 + \lambda \...
1k views

Rank of matrix with variable

$$\left( \begin{array} {ccc}1 & 1 & x \\ 1 & x & 1 \\ x & 1 & 1 \\ \end{array} \right)$$ Find the values of $x$ such that the matrix above has rank $1$, $2$ and $3$. ...
Completion of $2 \times 2$ positive semidefinite rank-$1$ partial matrix
This question is related to one property of rank-$1$, positive semidefinite matrices. Would be very useful in SDP problems (which is where I found it). Consider a $3 \times 3$ positive semidefinite ...
Suppose we have a real, symmetric matrix $A(x_1,x_2,x_3)$ given by \begin{pmatrix} a_{1,1} & a_{1,2} & x_1 & x_2 \\ a_{2,1} & a_{2,2} & a_{2,3} & x_3 \\ x_1 & a_{3,2} & ...