In matrix completion, the starting point is often stated as: the optimization problem for matrix completion:

$$\begin{array}{ll} \text{minimize} & \frac 12 \| X - M \|^2\\ \text{subject to} & \mbox{rank} (X) \leq r\end{array}$$

where $X$ is the reconstructed matrix and $M$ are the starting samples (the sparse matrix), and $r$ is some rank boundary.

My question is: where does the $\frac 12$ come from? Is it an error in the paper I'm reading or am I missing some basic step? ref: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=05459463

Thank you


1 Answer 1


The $\frac12$ is just a multiple to make things seem nicer, as it cancels out the square power if you differentiate the cost function $\|X-M\|^2$ with respective to the entries of $X$. Since $\|X-M\|^2$ and $\frac12\|X-M\|^2$ share the same minimizers, it's just a matter of taste to multiply by one-half.

By the way, I would call $\min_{\textrm{rank}(X)\le r}\|X-M\|^2$ a low-rank approximation problem rather than a matrix completion problem. To my understanding, a matrix completion problem is one that you need to fill in some missing entries of $M$, or modify some zero entries of $M$, so that the resulting matrix satisfies some requirement. In $\min_{\textrm{rank}(X)\le r}\|X-M\|^2$, the requirements are placed on $X$ rather than $M$, and existing nonzero entries of $M$ may change. So I wouldn't call it a "matrix completion problem". Yet different research communities have different usages of the term, so this is just my own opinion.

  • $\begingroup$ ok - thanks for clarifying my understanding! $\endgroup$
    – val
    Commented Nov 29, 2012 at 17:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .