Sparsification of Rectangular Matrices

✍ Scribed by S. Egner; T. Minkwitz

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 488 KB
• Volume: 26
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1998.0204

✦ Synopsis

Consider the problem of sparsifying a rectangular matrix with more columns than rows. This means forming linear combinations of the rows, while preserving the rank, such that the result contains as many zero entries as possible. A combinatorial search method is presented which sparsifies a matrix with exponentially many arithmetic operations in the worst case. Moreover, a method is presented which substantially reduces the combinatorial search space if the matrix gives rise to a non-trivial block structure.