Lemma 8.2, p. 11 — for A with independent columns, f^A has total curvature at most 1 − 1/κ²(A)

Let $A$ be a real $m \times n$ matrix whose columns $c_1, \dots, c_n \in \mathbb{R}^m$ are linearly independent, and let

be its condition number. Let $f^A(S) = \sum_{i=1}^n \|c_i - \mathrm{proj}_S(c_i)\|^2$ be the column-subset selection objective, a monotone decreasing set function on $[n]$. Then $f^A$ has total curvature at most $1 - 1/\kappa^2(A)$:

Equivalently, $c(f^A) = 1 - \min_j f^A_{[n]-j}(j)/f^A_\emptyset(j) \le 1 - 1/\kappa^2(A)$. The result ties a combinatorial parameter of the column-subset selection objective to the conditioning of the matrix, which is what lets the paper's curvature-dependent guarantees for supermodular minimization be quoted for column-subset selection.

Formalization Note "Non-singular" is read as linearly independent columns, the case in which §8 defines $\kappa(A)$ as a ratio. Curvature is written in the product form $f_{X-j}(j) \le (1-c)\,f_\emptyset(j)$, which is (1.1) multiplied out for a decreasing function. Under independence the supremum and infimum over the unit sphere are finite and positive, so $\kappa(A) \ge 1$ is a genuine real number. For $n = 0$ there is no $j$ and the statement is empty, as on the page.