Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

- LIPIcs-MFCS-2018-41
Final published version, 611 KB, PDF document

- https://doi.org/10.4230/LIPIcs.MFCS.2018.41
Final published version

- Chen Dan, Carnegie Mellon University ,
- Kristoffer Arnsfelt Hansen
- He Jiang, University of Southern California ,
- Liwei Wang, Peking University ,
- Yuchen Zhou, University of Wisconsin-Madison

Low rank approximation of matrices is an important tool in machine learning. Given a data matrix, low rank approximation helps to find factors, patterns, and provides concise representations for the data. Research on low rank approximation usually focuses on real matrices. However, in many applications data are binary (categorical) rather than continuous. This leads to the problem of low rank approximation of binary matrices. Here we are given a d × n binary matrix A and a small integer k < d. The goal is to find two binary matrices U and V of sizes d × k and k × n respectively, so that the Frobenius norm of A − UV is minimized. There are two models of this problem, depending on the definition of the dot product of binary vectors: The GF(2) model and the Boolean semiring model. Unlike low rank approximation of a real matrix which can be efficiently solved by Singular Value Decomposition, we show that approximation of a binary matrix is NP-hard, even for k = 1. In this paper, our main concern is the problem of Column Subset Selection (CSS), in which the low rank matrix U must be formed by k columns of the data matrix, and we are interested in the approximation ratio achievable by CSS for binary matrices. For the GF(2) model, we show that CSS has approximation ratio bounded by ^{k}
_{2} + 1 + _{2}(_{2k}
^{k}
_{−1}) and this is asymptotically tight. For the Boolean model, it turns out that CSS is no longer sufficient to obtain a bound. We then develop a Generalized CSS (GCSS) procedure in which the columns of U are generated from Boolean formulas operating bitwise on selected columns of the data matrix. We show that the approximation ratio achieved by GCSS is bounded by 2^{k−1} + 1, and argue that an exponential dependency on k is seems inherent.

Original language | English |
---|---|

Title of host publication | 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 |

Editors | Igor Potapov, James Worrell, Paul Spirakis |

Number of pages | 16 |

Volume | 117 |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Publication year | 2018 |

Pages | 41:1-41:16 |

Article number | 41 |

ISBN (print) | 9783959770866 |

DOIs | |

Publication status | Published - 2018 |

Event | 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, United Kingdom Duration: 27 Aug 2018 → 31 Aug 2018 |

Conference | 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 |
---|---|

Land | United Kingdom |

By | Liverpool |

Periode | 27/08/2018 → 31/08/2018 |

Series | Leibniz International Proceedings in Informatics |
---|---|

Number | 117 |

ISSN | 1868-8969 |

- Approximation algorithms, Binary matrices, Low rank approximation

See relations at Aarhus University Citationformats

No data available

ID: 134881022