Motivation
Unsupervised learning does not come with a single universal definition of a good group. Euclidean clustering rewards proximity to a center. Graph clustering rewards strong connections within groups and weak connections between them. Nonnegative factorization seeks additive parts of a matrix. These objectives can all be useful, but the same observations can yield different groupings when the geometry or representation changes.
Small samples add a second difficulty: a more flexible model can describe the observed data better while predicting less reliably. Choosing the number of clusters, representation dimension or regularization strength is itself a learning decision. If that choice repeatedly consults the test sample, the test sample becomes part of training. Mathematical optimization and trustworthy model evaluation therefore have to be taught together.
This unit derives several finite dimensional facts that make the methods understandable. It gives a worked foundation for k-means, spectral relaxation, nonnegative factorization, ridge regression and lasso.
Definitions
Definition 3.1.1
(The k-means objective)
Given and an integer , assignments and centers minimize
The usual alternating algorithm assigns each observation to a nearest center and then replaces each nonempty cluster's center by its mean. Empty clusters require a stated rule; an arbitrary replacement is not the mean of an empty set.
Euclidean distances depend on units. A coordinate measured in millimeters rather than meters has squared differences a million times larger. Standardizing coordinates changes the objective and can be appropriate, but its location and scale estimates must be learned using training data when predictive evaluation is intended.
Definition 3.1.2
(A weighted graph and its Laplacian)
Let be a symmetric matrix with nonnegative entries and zero diagonal. Define and the unnormalized Laplacian . Vertices are connected when joined by a path of positive-weight edges. For a vertex subset , its cut weight is .
A graph used for spectral clustering is a modeling choice. A distance kernel, a nearest-neighbor graph and a connectivity threshold can encode different neighborhoods. Symmetrization matters because the spectral statements below assume a symmetric matrix. The unnormalized formulation here is also distinct from normalized-cut formulations involving ; one should not exchange their eigenvectors without checking the objective.
Definition 3.1.3
(Nonnegative matrix factorization)
For nonnegative data , nonnegative matrix factorization, or NMF, chooses and to minimize, for example, . Each data column is then an additive combination of nonnegative columns of . The rank , loss and constraints are part of the problem definition. The joint optimization is generally nonconvex, despite being a convex quadratic in either factor when the other is fixed.
The additive interpretation should be read literally. A nonnegative coefficient cannot cancel a positive contribution from another part. This can make a representation easier to inspect when measurements themselves are additive quantities, but it does not prove that learned factors correspond to uniquely determined physical objects. Correlated parts can be redistributed across factors, and scaling ambiguities persist even in a perfect fit. Interpretability is a question to investigate, not a theorem obtained merely by imposing a sign constraint.
The unconstrained gradients of the squared loss are and . At a constrained stationary point a strictly positive coordinate must have zero corresponding gradient; a zero coordinate can have a nonnegative gradient, since only increasing it is feasible. This elementary condition already explains why unconstrained normal equations cannot simply be solved and then clipped to zero. Clipping changes the coupled optimum, and subsequent checks must use the constrained problem.
Definition 3.1.4
(Ridge and lasso objectives)
For a design matrix and response , the ridge objective is and the lasso objective is , where and . The soft-thresholding map at level sends a real number to .
Theorem/Proposition
Theorem 3.1.5
(Centroid optimality and alternating descent)
For a nonempty fixed cluster , its arithmetic mean uniquely minimizes . Consequently, a nearest-center assignment step followed by a mean update cannot increase the k-means objective, provided empty clusters are handled without increasing the objective. This descent statement does not imply a globally optimal clustering.
Theorem 3.1.6
(The Laplacian measures variation along edges)
For every ,
The nullspace consists exactly of vectors constant on each connected component. In particular, for a connected graph with at least two vertices, a minimizer of subject to and is an eigenvector for the second-smallest eigenvalue of .
Concept lensCombinatorial
The same energy as a cut count
For a vertex subset let be its indicator vector, equal to one on and zero elsewhere. In a pair contributes only when exactly one of lies in , and then . Each such unordered pair appears twice in the double sum, so , the cut weight. In the unit-weight path graph on three vertices, gives , the one edge leaving , while gives , the two edges leaving . The quadratic form on real vectors therefore extends the combinatorial count of broken edges to a continuous measure of variation along edges.
Theorem 3.1.7
(Ridge uniqueness and orthonormal lasso shrinkage)
For any real and , the objective has unique minimizer . If instead , the minimizer of has coordinates
Here every coefficient is penalized; an unpenalized intercept needs a separate specification.
Proof sketch or proof idea
Proof
(The centroid identity explains descent)
Write . Expanding and using gives
The second term proves uniqueness. For fixed centers, each assignment minimizes one summand independently. For fixed assignments, the centroid identity minimizes each nonempty cluster's contribution. Chaining these inequalities proves descent. The objective is bounded below by zero, so its values converge, but this fact alone does not prove that every possible tie-handling implementation terminates or finds the best partition.
Proof
(Graph energy and the spectral relaxation)
Expand the squares in the graph energy. Symmetry makes the two diagonal sums equal to , while the cross term is , giving . A zero sum of nonnegative weighted squares requires equal values across every positive edge, hence across every connected component; conversely such constants give zero energy.
For a connected graph choose an orthonormal eigenbasis with first vector and eigenvalues . A feasible vector has expansion with , so . Equality is attained in the second eigenspace. Discrete indicator vectors impose additional restrictions; relaxing them to real vectors explains why a final rounding step is necessary.
Proof X-ray
What is lost when a cut becomes an eigenvector
Energy equals cut weight only for the – indicator vectors . A real eigenvector need not be an indicator, and thresholding it changes both the vector and its constraints. The spectral theorem solves the relaxed quadratic problem exactly. It does not automatically prove that an arbitrary threshold gives a globally optimal balanced graph partition.
Proof
(Quadratic stabilization and sparse thresholding)
Ridge has gradient . For every nonzero , . Thus its stationary point is the unique minimum, even when is rank deficient.
Under , the lasso objective differs from by a constant. For a positive coordinate the derivative equation is and is feasible if ; the negative case gives if . At zero the subgradient condition is . These cases give soft thresholding. Without orthonormal columns the coordinates are coupled and this one-pass formula is generally false.
Counterexample mode
Soft thresholding fails without orthonormal columns
Consider the claim that for every design the lasso minimizer is with . Take one observation with two identical features: , and . Then and the formula proposes , with objective value
But has objective , which is smaller, so the formula does not produce a minimizer. Here . In fact, with the objective is at least , with equality exactly when the two coordinates do not have opposite signs, and this lower bound is smallest at , where it equals . The minimizers are therefore all with and , and they are not unique. Coordinatewise soft thresholding is exact only when ; for a general design the coordinates interact and the lasso must be solved as a coupled convex problem.
Worked examples
Ridge also has a useful singular-direction interpretation. If the nonzero singular values of the design are , its fitted coefficient along the corresponding right singular vector is the response's left-singular coordinate multiplied by . Unregularized inversion would multiply by . A tiny singular value can therefore amplify noise enormously in an ordinary inverse, while ridge suppresses that amplification. The price is shrinkage of genuine signal as well. Choosing the penalty concerns a bias–variance tradeoff, not a free improvement for every possible underlying coefficient vector. Moreover, changing a feature's scale changes its relative quadratic penalty unless scaling is explicitly accounted for.
Worked example 3.1.8
(A decreasing k-means iteration)
For observations , start with centers zero and ten. The nearest-center clusters are and , with objective . Their means are one and ten, reducing the objective to . The next assignment is unchanged. This certifies a stable alternating solution. A separate argument would be required to certify global optimality on a general dataset.
Worked example 3.1.9
(The path graph with three vertices)
Unit-weight edges connect vertices one to two and two to three. Then
The vectors , and are eigenvectors with eigenvalues zero, one and three. The unit, mean-zero vector has energy one, agreeing with the sum of its two squared edge differences. Its sign gives an ordering of vertices, but the middle zero requires a rounding convention. The graph itself is unchanged if the eigenvector's sign is reversed.
Worked example 3.1.10
(An additive factorization is not uniquely scaled)
The matrix has exact nonnegative rank-one factorization , . For any , the factors and give the same matrix and objective zero. Thus positivity does not identify the scale. Normalizing columns may fix this ambiguity, but does not generally establish uniqueness of a higher-rank factorization. A method constrained to nonnegative factors also cannot reconstruct a matrix containing a negative entry exactly.
Worked example 3.1.11
(Ridge shrinks while lasso can remove a coordinate)
Take , and . Ridge gives because each coefficient is divided by two. Lasso gives by soft thresholding. The zero is a consequence of the absolute-value corner, not numerical rounding. With a different normalization of the squared loss or penalty, numerical thresholds change; formulas should be derived for the exact written objective.
Model selection uses data to choose such quantities as , factor rank or . A validation set estimates performance after fitting on a separate training set. Cross-validation rotates the validation role across folds. Every data-dependent step, including scaling, feature screening and PCA, must be fitted inside each training fold and then applied to that fold's validation data. After selection, refitting on all development data is legitimate, but final evaluation requires an untouched test sample if one wants an independent assessment.
For a likelihood model with free parameters, common scores are and , with smaller preferred. Their motivations use different asymptotic arguments and regularity conditions. They are not universal finite-sample risk bounds. For instance, unrestricted mixtures have likelihood singularities and identification difficulties, so simply counting parameters does not establish that a regular-model BIC approximation is valid. Small samples make these qualifications particularly relevant. A validation comparison is also uncertain: a small numerical advantage does not establish a durable population advantage.
Common mistakes
Counterexample mode
Stable k-means can miss a better partition
For data and two centers at two and seven, assignments are and . Each center already equals its cluster mean, so alternating steps do nothing. The objective is . But clusters and with means zero and six have objective . Descent and stability therefore cannot serve as global certificates.
Common mistake
(A small sample cannot support unlimited model searching)
Trying many hyperparameters and reporting the best test result selects favorable test noise. Reusing the test set this way changes its statistical role even if no gradient was computed on it. Likewise, fitting a scaling transform on all observations before cross-validation transfers information across the split. Keep the complete selection procedure inside the development data, and report evaluation uncertainty rather than declaring every small difference meaningful.
Summary
Centroid updates optimize fixed k-means assignments; Laplacian eigenvectors optimize a relaxed graph energy; NMF imposes additive nonnegative structure. Ridge stabilizes all coefficient directions, while lasso can set coordinates exactly to zero. Each method solves a specified objective, and choosing that objective or its complexity is part of learning. Sound evaluation must account for that choice.
Exercises
Quick check
(For a cluster containing zero, two and seven, find its optimal center and minimum squared error. State the extra error caused by using center four.)
Use the centroid identity rather than expanding a new quadratic twice.
Solution · Answer
The mean is three and the minimum squared error is . A center of four adds , giving total 29. The multiplier is the cluster size, not its dimension.
Quick check
(A graph has two components: a unit edge joining vertices one and two, and an isolated third vertex. Describe the Laplacian nullspace and its dimension.)
An isolated vertex is a connected component.
Solution · Answer
The Laplacian is . Its nullspace is and has dimension two, spanned by and . Requiring only a single global constant would miss the disconnected component.
Quick check
(Let X have one row (1,1), y equal two and ridge parameter one. Find its ridge coefficients. Compare the uniqueness with unregularized least squares.)
Use the exact half-squared-loss convention in the theorem.
Solution · Answer
The ridge equations are , so . Without the penalty, all vectors with minimize squared error. Ridge chooses a unique biased fit with sum ; it does not preserve exact interpolation merely because interpolation is possible.
Quick check
(Under an orthonormal design, and the lasso parameter is 0.5. Find the coefficients and explain what happens at the threshold equality.)
Use the subgradient condition at zero.
Solution · Answer
Soft thresholding gives . At , zero satisfies the subgradient condition and is the unique scalar minimizer because the quadratic term is strictly convex. A coefficient becoming zero at equality does not produce a continuum of minimizers.