Optimization Online


Computing the Spark: Mixed-Integer Programming for the (Vector) Matroid Girth Problem

Andreas M. Tillmann(tillmann***at***or.rwth-aachen.de)

Abstract: We investigate the NP-hard problem of computing the spark of a matrix (i.e., the smallest number of linearly dependent columns), a key parameter in compressed sensing and sparse signal recovery. To that end, we identify polynomially solvable special cases, gather upper and lower bounding procedures, and propose several exact (mixed-)integer programming models and linear programming heuristics. In particular, we develop a branch & cut scheme to determine the girth of a matroid, focussing on the vector matroid case, for which the girth is precisely the spark of the representation matrix. Extensive numerical experiments demonstrate the effectiveness of our specialized algorithms compared to general-purpose black-box solvers applied to several mixed-integer programming models.

Keywords: Matroid Girth, Spark, Compressed Sensing, Branch and Cut, Mixed-Integer Programming

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 03/14/2018
Entry Accepted: 03/15/2018
Entry Last Modified: 03/14/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society