Matrix completion and extrapolation via kernel regression

With only a subset of its entries available, matrix completion (MC) amounts to recovering the unavailable entries by leveraging just the low-rank attribute of the matrix itself [1]. The relevant task arises in applications as diverse as image restoration [2], sensor networks [3], and recommender systems [4]. To save power for instance, only a fraction of sensors may collect and transmit measurements to a fusion center, where the available spatiotemporal data can be organized in a matrix format, and the unavailable ones can be eventually interpolated via MC [3]. Similarly, collaborative filtering of ratings given by users to a small number of items are stored in a sparse matrix, and the objective is to predict their ratings for the rest of the items [4]. Existing MC approaches rely on some form of rank minimization or low-rank matrix factorization. Specifically, [1] proves that when MC is formulated as the minimization of the nuclear norm subject to the constraint that the observed entries remain unchanged, exact recovery is possible under mild assumptions; see also [5] where reliable recovery from a few observations is established even in the presence of additive noise. Alternatively, [4] replaces the nuclear norm by a product of two low-rank factor matrices that are identified in order to recover the complete matrix. While the low-rank assumption can be sufficient for reliable recovery, prior information about the unknown matrix can be also accounted to improve the completion outcome. Forms of prior information can include sparsity [3], local smoothness [6], and interdependencies encoded by graphs [7]-[10].