Matrix factorization with Binary Components

2014/01/23 by Martin Slawski, Matthias Hein, Slawski, Martin +3 · 1 citation
Computer Science · Engineering · #Error Correcting Code Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1401.6024

openalex publication_date 2014/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Motivated by an application in computational biology, we consider low-rank matrix factorization with \0,1\-constraints on one of the factors and optionally convex constraints on the second one. In addition to the non-convexity shared with other matrix factorization schemes, our problem is further complicated by a combinatorial constraint set of size 2^{m ⋅ r}, where m is the dimension of the data points and r the rank of the factorization. Despite apparent intractability, we provide - in the line of recent work on non-negative matrix factorization by Arora et al. (2012) - an algorithm that provably recovers the underlying factorization in the exact case with O(m r 2^r + mnr + r² n) operations for n datapoints. To obtain this result, we use theory around the Littlewood-Offord lemma from combinatorics.

Cited by

• Binary Quadratic Quantization: Beyond First-Order Quantization for Real-Valued Matrix Compression

Related

• Binary component decomposition Part II: The asymmetric case
• Factorization of Binary Matrices: Rank Relations, Uniqueness and Model Selection of Boolean Decomposition
• Notes on Low-rank Matrix Factorization
• Factoring nonnegative matrices with linear programs
• Binary Component Decomposition Part I: The Positive-Semidefinite Case