Lifelong Matrix Completion with Sparsity-Number
This work addresses matrix completion for data analysis applications, presenting an incremental improvement in algorithm efficiency.
The paper tackles the matrix completion problem by proposing a single-phase column space recovery algorithm based on sparsity-number, which is extended to a two-phase exact matrix completion algorithm, showing efficiency comparable to multi-phase methods.
Matrix completion problem has been previously studied under various adaptive and passive settings. Previously, researchers have proposed passive, two-phase and single-phase algorithms using coherence parameter, and multi phase algorithm using sparsity-number. It has been shown that the method using sparsity-number reaching to theoretical lower bounds in many conditions. However, the aforementioned method is running in many phases through the matrix completion process, therefore it makes much more informative decision at each stage. Hence, it is natural that the method outperforms previous algorithms. In this paper, we are using the idea of sparsity-number and propose and single-phase column space recovery algorithm which can be extended to two-phase exact matrix completion algorithm. Moreover, we show that these methods are as efficient as multi-phase matrix recovery algorithm. We provide experimental evidence to illustrate the performance of our algorithm.