Proof. The problem of computing the multiscale simplicial flat norm of T (Equation 2.5) is cast as the optimization problem given in Equation (2.7). This problem is reformu- lated as an instance of ILP (Equation 2.8). We get the multiscale simplicial flat norm LP (Equation 2.9) by relaxing the integrality constraints of this ILP. As noted in Remark 2.2.1, the optimal cost of this LP is finite. The polyhedron of this LP has at least one vertex, given that all variables are nonnegative [7, Cor. 2.2]. By Lemma 2.3.2, the con- straint matrix of this LP is totally unimodular, as [ ∂$_{d}$$_{+1}$ ] is so. Hence by Theorem 2.3.1, all vertices of the feasible region of the multiscale simplicial flat norm LP are integral, since t ∈ Z $^{m}$. 

An optimal solution ( x + ∗ , x − ∗ , s + ∗ , s − ∗ ) of the multiscale simplicial flat norm LP can be found in polynomial time using an interior point method [7, Chap. 9]. If it happens to be a unique optimal solution, then it will be a vertex, and hence will be integral by Theorem 2.3.1. Hence it is an optimal solution to the ILP (Equation 2.8). 

If the optimal solution is not unique, then ( x + ∗ , x − ∗ , s + ∗ , s − ∗ ) may be nonintegral. But since the optimal cost is finite, there must exist a vertex in its polyhedron that has this minimum cost. Given a nonintegral optimal solution obtained by an interior point method, one can find such an integral optimal solution at a vertex in polynomial time [23]. Hence the multiscale simplicial flat norm ILP can be solved in polynomial time in this case as well. 

Remark 2.3.4. We point out that since the boundary matrix B = [ ∂$_{d}$$_{+1}$ ] has entries only in {− 1 , 0 , 1 } , the constraint matrix of the multiscale simplicial flat norm LP (Equa- tion 2.9) also has entries only in {− 1 , 0 , 1 } . Hence the multiscale simplicial flat norm LP can be solved in strongly polynomial time [43], i.e., the time complexity is indepen- dent of the objective function and right-hand side coefficients, and depends only on the dimensions of the problem. 

