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 rank matrix $\hat{M}$ that interpolates the known entries of $M$. I know a way to solve this problem is to solve the following minimization problem (Maximum Margin Matrix Factorization)

$\min_{A \in \mathbb{R}^{m \times r}, B \in \mathbb{R}^{n \times r}} \|P_\Omega(M) - P_\Omega(AB^T)\|^2_F + \lambda(\|A\|^2_F + \|B\|^2_F)$

Where $\hat{M} = A B$. I know the problem above can be solved by using SVD or ALS.

But I was wondering what if the elements of $M$ have some constraint such as $~C M = 0_{m \times n}$, where $C \in \mathbb{R^{m \times m}}$, i.e., $C \hat{M} = C (AB) = 0$. How could I solve the Matrix Completion with this new constraint? Is it possible to solve it by using ALS?


Putting aside recovery guarantee, I think there are at least two naive approaches.

If your constraint can be solved for some variables in A or B

In this case you can try parameter sharing with ALS. This means to set some parameters dependent in the optimization i.e. use the smaller set of variables to calculate the estimate, as well as learn them by differentiating the loss function with respect to the smaller set of variables.

If C is more complex and cannot be solved easily

In this case, try adding a penalty to the loss function e.g. $\lambda \|CAB\|_F^2$ . I think the gradient of the penalty term with respect to A or B can be calculated analytically. It should work in the gradient as a shrinking force to keep your solution within the set that satisfy the constraints. This time, again with ALS.

I am sure there are general theoretical guarantee that can handle the case (because the added constraints are still linear), but if you just want a quick result, you can try these heuristics with cross validation first.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.