Degrees of freedom in submodular regularization: a computational perspective of Stein's unbiased risk estimate (Q2293382)

This paper studies regularized estimators obtained by means of two polyhedral convex classes of regularizators for the regression model defined through submodular functions, the Lovász extension regularization and submodular norm regularization. Characterizations are obtained for the degrees of freedom of the submodular regularization estimators. It is shown that their degrees of freedom can be represented in terms of partitions induced by the estimators. Unified representations of the degrees of freedom are derived, which are independent of the choices of the design matrix and of the penalty function. If the design matrix has full column rank, calculating an unbiased estimator of the degrees of freedom requires an additional computational cost of only \(O(p \log p)\) after a solution for the estimator is obtained, for \(p\) the dimension of the parameter. Relationships between submodular regularization estimators and projection and anti-projection estimators are established. The submodular regularization estimators are shown to be special cases of anti-projection estimators with respect to certain classes of polyhedra, so that general results for anti-projection estimators are valid for them. Specific examples of submodular regularization estimators are studied and numerical simulations are conducted to investigate their empirical performance.