# Matrix completion by rank minimization

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

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.