spark

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

  • Andreas M. Tillmann
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Graphs and Matroids Tags , , , ,

    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 … Read more

    New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Global Optimization Tags , , , , ,

    The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more