A Threshold-Search Projected Gradient Method for Graph-Cut Optimization

Many graph-cut clustering models can be formulated as the minimization of differentiable functions over one-hot assignment matrices. Projected gradient (PG) methods provide a natural first-order approach for such problems. Their usual stepsize strategies, however, may lead to stagnation due to the discreteness of the feasible set: once the stepsize is sufficiently small, the projection returns the current assignment matrix unchanged. To address this issue, we characterize the threshold structure of the projection mapping with respect to the projection parameter. We show that it is piecewise constant and can change only at a finite set of explicitly computable row-wise thresholds. Building on this structure, we propose the Threshold-Search Projected Gradient (TSPG) method, which searches directly over this finite set of thresholds rather than continuously adjusting the stepsize. TSPG accepts successive trial moves that satisfy sufficient decrease and terminates after finitely many outer iterations. For graph-cut objectives, we further derive incremental updates that reduce the cost of objective and gradient evaluations. Experimental results demonstrate the effectiveness and computational efficiency of TSPG compared with existing graph-cut solvers.