Friday, February 21, 2014

Interest Zone Matrix Approximation - implementation -



Interest Zone Matrix Approximation by Gil Shabat, Amir Averbuch

Abstract. We describe an algorithm for matrix approximation when only some of its entries aretaken into consideration. The approximation constraint can be any whose approximated solution isknown for the full matrix. For low rank approximations, this type of algorithms appears recently inthe literature under different names, where it usually uses the Expectation-Maximization algorithmthat maximizes the likelihood for the missing entries without any relation for mean square errorminimization. In this paper, we show that the algorithm can be extended to different cases otherthan low rank approximations under Frobenius norm such as minimizing the Frobenius norm undernuclear norm contraint, spectral norm constraint, orthogonality constraint and more. We also discussthe geometric interpretation of the proposed approximation process and its optimality for conexconstraints and show how the approximation algorithm can be used for matrix completion undera variety of spectral regularizations. Its applications to physics, electrical engineering and datainterpolation problems are also described.

Abstract—We describe several algorithms for matrix completion and matrix approximation when only some of its entries are known. The approximation constraint can be any whose approximated solution is known for the full matrix. For low rank approximations, similar algorithms appear recently in the literature under different names. In this work, we introduce new theorems for matrix approximation and show that these algorithms can be extended to handle different constraints such as nuclear norm, spectral norm, orthogonality constraints and more that are different than low rank approximations. As the algorithms can be viewed from an optimization point of view, we discuss their convergence to global solution for the convex case. We also discuss the optimal step size and show that it is fixed in each iteration. In addition, the derived matrix completion flow is robust and does not require any parameters. This matrix completion flow is applicable to different spectral minimizations and can be applied to physics, mathematics and electrical engineering problems such as data reconstruction of images and data coming from PDEs such as Helmholtz’s equation used for electromagnetic waves.

No comments:

Printfriendly