Binary matrix completion with performance guarantees for single individual haplotyping

Abstract

We study the problem of approximating a partially observed matrix by a product of two low-rank matrices where the data as well as the factors are constrained to be binary. This computationally challenging task is motivated by the single individual haplotyping problem which attracted considerable attention in computational biology and is of critical importance for personalized medicine applications. We analyze a binary-constrained variant of the alternating minimization algorithm for solving the aforementioned problem in the scenario where the matrices are rank-one, establish its performance and convergence properties, and in doing so provide the first theoretical guarantees for haplotype reconstruction expressed in terms of the minimum error-correction score. Sample complexity required for reconstruction is derived and experiments are performed on both synthetic and real datasets, demonstrating superiority of the proposed framework over competing methods.