论文标题
针对大规模跟踪的原始二重式求解器
A Primal-Dual Solver for Large-Scale Tracking-by-Assignment
论文作者
论文摘要
我们为组合问题提出了一个快速近似求解器，称为按分配跟踪，我们适用于细胞跟踪。后者在许多生命科学中，尤其是在细胞和发育生物学中的发现中起着关键作用。到目前为止，在最通用的设置中，诸如Gurobi等现成的求解器解决了这个问题，Gurobi等现成的求解器随着输入的大小而迅速增长。相反，对于我们的方法，这种增长几乎是线性的。 我们的贡献包括一个新的（1）可分解的问题。 （2）以优化基于分解双重的双重级坐标上升方法； （3）原始启发式方法根据双重信息重建可行的整数解决方案。与解决Gurobi的问题相比，我们观察到了高达约60〜的速度，同时大大减少了记忆足迹。我们证明了我们方法对现实世界跟踪问题的功效。
We propose a fast approximate solver for the combinatorial problem known as tracking-by-assignment, which we apply to cell tracking. The latter plays a key role in discovery in many life sciences, especially in cell and developmental biology. So far, in the most general setting this problem was addressed by off-the-shelf solvers like Gurobi, whose run time and memory requirements rapidly grow with the size of the input. In contrast, for our method this growth is nearly linear. Our contribution consists of a new (1) decomposable compact representation of the problem; (2) dual block-coordinate ascent method for optimizing the decomposition-based dual; and (3) primal heuristics that reconstructs a feasible integer solution based on the dual information. Compared to solving the problem with Gurobi, we observe an up to~60~times speed-up, while reducing the memory footprint significantly. We demonstrate the efficacy of our method on real-world tracking problems.
