recovery guarantee

Rank-one Boolean tensor factorization and the multilinear polytope

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Cutting Plane Approaches, Linear Programming Tags , , ,

    We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the … Read more

    Efficient Joint Object Matching via Linear Programming

  • Antonio De Rosa
  • Aida Khajavirad
    • Categories Cutting Plane Approaches, Integer Programming, Linear Programming Tags , , , ,

    Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear … Read more