  A usual way to model a recommendation system is as a matrix completion
problem. There are several matrix completion methods, typically using
optimization approaches or collaborative filtering. Most approaches assume that
the matrix is either low rank, or that there are a small number of latent
variables that encode the full problem. Here, we propose a novel matrix
completion algorithm for recommendation systems, without any assumptions on the
rank and that is model free, i.e., the entries are not assumed to be a function
of some latent variables. Instead, we use a technique akin to information
theory. Our method performs hybrid neighborhood-based collaborative filtering
using Kolmogorov complexity. It decouples the matrix completion into a vector
completion problem for each user. The recommendation for one user is thus
independent of the recommendation for other users. This makes the algorithm
scalable because the computations are highly parallelizable. Our results are
competitive with state-of-the-art approaches on both synthetic and real-world
dataset benchmarks.
