Parameterized low-rank binary matrix approximation

DOI10.1007/s10618-019-00669-5zbMath1458.68075arXiv1803.06102OpenAlexW2963651520WikidataQ126414020 ScholiaQ126414020MaRDI QIDQ2218414

Fahad Panolan, Fedor V. Fomin, Petr A. Golovach

Publication date: 15 January 2021

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.06102

zbMATH Keywords

clusteringbinary matriceslow-rank approximationfixed-parameter tractability

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Approximation algorithms (68W25) Boolean and Hadamard matrices (15B34) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Parameterized complexity of categorical clustering with size constraints ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Lossy kernelization of same-size clustering ⋮ Lossy kernelization of same-size clustering

Uses Software

• PROXIMUS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discovery of optimal factors in binary data via a novel method of matrix decomposition
• Reducing rank of the adjacency matrix by graph modification
• Fundamentals of parameterized complexity
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• Non-negative matrix factorization techniques. Advances in theory and applications
• On problems without polynomial kernels
• Application of separability and independence notions for proving lower bounds of circuit complexity
• Expressing combinatorial optimization problems by linear programs
• Optimal decompositions of matrices with grades into binary and graded matrices
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• The complexity of the single individual SNP haplotyping problem
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Rank Reduction of Directed Graphs by Vertex and Edge Deletions
• Computational Advertising: Techniques for Targeting Relevant Ads
• Generalized Independent Component Analysis Over Finite Alphabets
• Robust principal component analysis?
• Approximating extent measures of points
• Rank-Sparsity Incoherence for Matrix Decomposition
• Randomized Algorithms for Matrices and Data
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Closest Substring Problems with Small Distances
• Complexity Lower Bounds using Linear Algebra
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximate clustering via core-sets
• Spectral Algorithms
• Color-coding
• A Clustering Approach to Constrained Binary Matrix Factorization
• On the Parameterized Complexity of Biclique Cover and Partition
• Computing approximate PSD factorizations
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Kernelization
• On Two Segmentation Problems
• Approximation Schemes for Low-rank Binary Matrix Approximation Problems
• A PTAS for ℓ_p-Low Rank Approximation
• Independent Component Analysis Over Galois Fields of Prime Order
• Learning the parts of objects by non-negative matrix factorization
• Weighted low rank approximations with provable guarantees
• Fast biclustering by dual parameterization
• Data reduction and exact algorithms for clique cover
• Computing a nonnegative matrix factorization -- provably
• Discovery Science
• Low-Rank and Sparse Modeling for Visual Analysis
• Segmentation problems
• Parameterized Algorithms
• An Almost Optimal Algorithm for Computing Nonnegative Rank

This page was built for publication: Parameterized low-rank binary matrix approximation