Motivation
A low-rank approximation theorem describes an optimum, but it does not by itself tell us how to prepare observations, compute the representation or use it on a new observation. Three choices enter before an eigensolver runs: which observations may determine the center, which coordinates define the reconstruction loss and how many directions will be retained. These are modeling decisions. An accurate eigensolver cannot repair an inappropriate choice of loss or information leaked from evaluation data.
There is also a distinction between a good reconstruction and a stable direction. When two leading variances are almost equal, many directions reconstruct almost equally well. A small change in the data can then rotate a reported loading substantially while barely changing the objective. Conversely, an iterative computation can return an exact eigenvector that is the wrong one. To read an output responsibly, we need the optimization problem, a finite convergence argument and a statement of what a spectral gap actually controls.
This section develops these ideas for real finite matrices. The results below concern the observed matrix and specified perturbations. Turning them into population guarantees would require a sampling model and a bound on covariance estimation error, neither of which is assumed here.
Definitions
Definition 21.1.1
(Training-centered data and reconstruction loss)
Let be the training observations, with . Set
The divisor makes the eigenvalues of equal to mean squared scores; using rescales those eigenvalues but preserves their eigenvectors. If has orthonormal columns, put . The scores are , reconstructed centered rows are , and training reconstruction loss per observation is .
The uncentered reconstructed observations are obtained by adding back to each row. For a new column-vector observation , the locked training representation gives score and reconstruction . Replacing the center with the evaluation-set mean changes the fitted procedure. Choosing or a coordinate scaling from validation data is possible, but the whole choice must then remain inside model selection; the final test observations must remain outside it.
Definition 21.1.2
(Singular values and two different errors)
Write an SVD as , with and . Pad the singular-value list with zeros up to , completing singular vectors to orthonormal bases where needed. The truncated matrix is , where . The Frobenius norm is the square root of the sum of squared matrix entries, so . The spectral norm is
Thus spectral approximation controls the largest error over unit input combinations; Frobenius approximation controls the total squared error. They are different objectives, even though the truncated SVD solves both.
For , the leading right singular vectors are leading eigenvectors of , with eigenvalues . Directions in the nullspace may complete a basis when . In either case, keeping a leading -dimensional eigenspace gives , with the SVD chosen to have leading right singular vectors spanning that selected space. At a repeated singular value, an arbitrary fixed SVD need not have this compatibility. The Frobenius approximation result, proved again below in the proof section, therefore yields training loss . Centering implies ; small samples can force zero eigenvalues without implying that the population has no variation in those directions.
Theorem/Proposition
Theorem 21.1.3
(The exact best spectral-norm rank bound)
For any real matrix and integer ,
The truncated SVD attains the spectral bound. Equal singular values at the truncation point allow different leading subspaces; this theorem does not assert uniqueness of a spectral-norm minimizer, even when a gap is present.
Theorem 21.1.4
(A finite leading-direction perturbation bound)
Let be a real symmetric matrix, with , eigenvalues , unit leading eigenvector and gap . Let be symmetric with . Its leading eigenvector is unique up to sign. Define the unoriented angle by . Then
The theorem applies in particular to sample covariance matrices, provided the displayed error bound and gap are actually available. It does not supply an estimation-error bound from data alone.
Theorem 21.1.5
(Power iteration needs an initial leading component)
Let be positive semidefinite with . Expand a unit starting vector as in an orthonormal eigenbasis, and assume . Define . If is its unoriented angle to , then, for ,
Normalizing after each multiplication produces the same directions in exact arithmetic. The statement does not guarantee a leading direction when . A repeated leading eigenvalue lies outside its strict-gap hypotheses; simply substituting a ratio of one gives no strict contraction bound for a prescribed loading. We state the bound for to avoid a zero-to-zero power convention when .
Proof sketch or proof idea
Proof
(A rank-deficient map must miss one leading combination)
When , extend the right singular vectors through using an orthonormal nullspace basis; this is possible because . Let be the span of the first right singular vectors. This space has dimension . A matrix of rank at most cannot be injective on , so there is a unit with . Orthogonality of the left singular vectors gives
Consequently every admissible has spectral error at least . The residual has singular values , so its spectral norm equals this lower bound and its squared Frobenius norm is the stated sum. This also handles zero singular values. The argument proves attainment and the value; it does not identify every minimizing matrix.
For completeness, the Frobenius optimality can also be proved here. Let be the orthogonal projector onto the row space of . Since , orthogonality of complementary right projections gives
In a complete orthonormal right-singular basis, taking for , write . Each is in and their sum is . Thus : allocating at most units of mass to the largest nonnegative weights maximizes the sum. Subtracting proves the Frobenius lower bound, attained by . This proof uses no full-rank assumption and makes the distinction between the two approximation objectives explicit.
Proof X-ray
A dimension count, then a weighted average
The real idea is a dimension count: a matrix of rank at most cannot be injective on the -dimensional space , so some unit has , and the error on is just . Orthogonality of the left singular vectors turns into a weighted average of , which is at least by the ordering. The rank hypothesis enters only in the count. The argument gives the value of the minimum and says nothing about which matrices attain it.
Proof
(The gap allows inversion only away from the leading direction)
For every unit , . Evaluating the Rayleigh quotient of at proves . Its second eigenvalue is at most : restrict the Rayleigh quotient to , where , and apply the symmetric min–max characterization. Hence , proving uniqueness up to sign.
Put and . Projecting onto gives
On this subspace, every eigenvalue of the operator on the left is at least . Its inverse has norm at most . Therefore , which is the angle bound. To obtain the projector identity, change the sign of if necessary and write for a unit . On the span of , the difference of projectors has trace zero and determinant , hence eigenvalues ; it vanishes on the orthogonal complement. The coincident-direction case has zero difference directly. The inverse step itself needs only ; the stronger stated half-gap condition also guarantees a simple perturbed leading eigenvalue and an angle bound strictly below one.
Proof X-ray
An observed gap and a statistical guarantee are separate ingredients
The inverse bound uses the population-or-reference matrix gap and an independently justified perturbation size . A large leading eigenvalue alone is insufficient: it may be almost tied with the second. If is a population covariance and its estimate, a sampling argument must first establish a bound on . The algebra here then turns that bound into a direction bound. It cannot establish the missing premise from a visually attractive loading plot.
Proof
(Track the unwanted eigencomponents before normalizing)
The leading coefficient of is . The squared norm of all other coefficients is . Their ratio proves the tangent bound and also proves that the normalization denominator is nonzero. Expanding a unit in the same eigenbasis gives
All eigenvalues are nonnegative, so the largest unwanted magnitude is . For a general symmetric matrix this need not hold: ordinary power iteration follows the eigenvalue with largest absolute value, which may be negative. Covariance matrices avoid that particular problem, but not a zero starting component or finite-precision error.
Worked examples
Worked example 21.1.6
(Fit, compress and reconstruct every observation)
Take four training observations , , and . Their mean is . Centered rows are , , and , so
The unit eigenvectors are , , with eigenvalues eight and two. The singular values of are and . Keeping one direction gives scores . Multiplying each score by reconstructs centered rows . Adding the training mean gives .
Each residual has squared length two, so total squared reconstruction error is eight and error per observation is two. This agrees with . Spectral error is instead ; it is neither the squared Frobenius error nor the per-observation loss. The retained variance fraction is , a training reconstruction description rather than a classification-accuracy statement.
For a new observation , the centered vector is , its score is , and its reconstruction is . Squared reconstruction error is two. No evaluation-set centering or recomputation of directions occurs in this calculation.
Worked example 21.1.7
(Execute power iteration and interpret the stopping evidence)
For the same , start at . Then is proportional to , so and
One multiplication gives and quotient . Two give and quotient . The following standard-library program executes the normalized iteration; the fixed four-step budget is explicit, so a stopping rule is not being silently inferred from the output.
from math import sqrt
z = (1.0, 0.0)
for t in range(5):
Cz = (5*z[0] + 3*z[1], 3*z[0] + 5*z[1])
rayleigh = z[0]*Cz[0] + z[1]*Cz[1]
residual = sqrt(sum((Cz[j] - rayleigh*z[j])**2 for j in range(2)))
print(t, f"{rayleigh:.9f}", f"{residual:.9f}")
if t < 4:
length = sqrt(Cz[0]**2 + Cz[1]**2)
z = (Cz[0]/length, Cz[1]/length)
0 5.000000000 3.000000000
1 7.647058824 1.411764706
2 7.976653696 0.373540856
3 7.998535514 0.093727117
4 7.999908449 0.023437142
The residual measures approximate eigenvector status. Identifying this eigenvector as leading uses the nonzero initial component and the positive spectral gap. In a large matrix, an implementation may apply without storing . Direct SVD avoids explicitly forming a covariance matrix, whose ratio of largest to smallest nonzero eigenvalue is the square of the corresponding singular-value ratio of . Neither approach removes the need to center the training matrix or respect the chosen loss. The program uses floating-point arithmetic; its printed values agree with the exact quantities and to the displayed precision. A general floating-point error analysis and general-purpose eigensolver are beyond this two-dimensional example.
Worked example 21.1.8
(A gap turns an off-diagonal perturbation into an angle bound)
Let and have diagonal zero and both off-diagonal entries . Its spectral norm is , and . The theorem therefore gives . Direct diagonalization gives
The exact angle satisfies the bound, which is useful without being an equality. By contrast, changes its leading direction from to under , whose norm is . As , arbitrarily small perturbations cause a right-angle change because the reference gap also vanishes. The strict small-perturbation hypothesis fails, exactly where it should.
Concept lensStructural
Subspace stability, reconstruction and label information answer different questions
A repeated leading eigenvalue can make an individual loading nonidentifiable while its full eigenspace remains meaningful. A tiny gap can make a loading unstable while reconstruction remains good. Even a stable, high-variance direction can omit class information. For example, equally likely Gaussian classes with means and and common within-class covariance have total covariance . The leading principal coordinate has exactly the same distribution in both classes and therefore contains no label information. Report the chosen rank, training loss, gap and evaluation target separately; none is a substitute for the others.
Common mistakes
Counterexample mode
Zero residual can certify the wrong eigenvector
For , starting power iteration at leaves it at forever. Its residual is exactly zero, yet its Rayleigh quotient is one rather than four. A small residual alone does not prove that the leading component was found. The theorem requires a nonzero leading starting coefficient, and the example violates that condition. Random starts can reduce this failure risk under appropriate distributions, but a claim of deterministic success still needs its premises.
Common mistake
(Centering and changing units change the question being optimized)
For observations and , the uncentered second-moment matrix is . An uncentered rank-one fit keeps the first axis and spends its capacity representing the mean. The centered covariance is , so centered PCA keeps the second axis and reconstructs both observations exactly after adding the mean back. Both computations can be numerically correct while solving different problems.
Likewise, if centered covariance is , multiplying the first coordinate by changes it to . The leading direction changes from the first axis to the second. Euclidean reconstruction after rescaling weights original-coordinate squared errors by the squares of those scale factors. It is therefore essential to state units and the loss before calling a representation optimal. Training-estimated standardization is a legitimate alternative metric, not an invariant version of raw-coordinate PCA.
Summary
Training-centered SVD supplies scores and a complete reconstruction rule for new observations. Truncation minimizes both total squared matrix error and worst unit-combination error, with different reported values. A spectral gap converts a justified matrix perturbation bound into direction stability. For positive semidefinite matrices, the proved bound gives geometric convergence to the leading direction when the start has a nonzero leading component and . A repeated leading eigenvalue lies outside this theorem, so this bound does not select a prescribed loading in that case. These finite statements support careful computations; they do not establish predictive performance or an unknown population covariance.
Exercises
Quick check
(In the four-observation fit, reconstruct the new observation using the locked rank-one representation. Compute its squared error and explain why its second score need not be retained.)
Subtract the training mean before taking the leading score.
Solution · Answer
The centered observation is , with leading score . Its reconstructed centered vector is , so the reconstruction is . The residual is and squared error eight. Its discarded second score is , whose square is also eight. Rank one deliberately discards that coordinate; a large error on this observation does not invalidate the training optimum. It shows that the chosen representation may reconstruct this observation poorly. Changing rank in response would be a new modeling decision requiring the intended selection protocol.
Quick check
(For the power-iteration example, find the smallest nonnegative integer for which the tangent of the leading-direction angle is at most . Compute the exact Rayleigh error at that iteration.)
The exact tangent is a power of one quarter.
Solution · Answer
We need . Since and , the smallest iteration is five. The exact Rayleigh error is , approximately . This is a deterministic computation for the given matrix and initial vector, not a universal five-iteration rule. Starting nearer the orthogonal complement would increase the necessary budget through the initial tangent factor.
Quick check
(A symmetric reference covariance has leading eigenvalues and . An independent argument bounds the covariance perturbation spectral norm by . Bound the leading-projector error in the spectral norm. Does the same argument certify a bound strictly below one when only a perturbation bound of is known?)
Check the theorem's strict hypothesis before substituting numbers.
Solution · Answer
The gap is two and , so the projector error is at most . With only , the strict hypothesis fails. Substitution would give one, which is the trivial upper bound between rank-one orthogonal projectors and supplies no strict directional control. Indeed plus has a repeated leading eigenvalue six; an orthogonal leading direction is then allowed. No unique perturbed leading line is certified.
Quick check
(Let and retain rank one. Give a truncated optimum, both approximation errors and a different spectral-norm optimum. Explain why the Frobenius-optimal rank-one matrix is nevertheless unique here.)
The spectral objective can tolerate a small change in the retained diagonal entry while the discarded value three remains the largest error.
Solution · Guided solution
The truncated matrix is . Spectral error is three, while squared Frobenius error is and Frobenius error is . The different rank-one matrix still has spectral error , so it is also spectrally optimal. Indeed every with has spectral error three. Its squared Frobenius error at is eleven. For Frobenius rank-one approximation the strict gap forces the row-space trace bound above to use , and equality in the complementary-projection bound requires . This fixes the coefficient at five and both leading singular lines. Thus the Frobenius-optimal matrix is unique, although the two individual unit singular vectors can both have their signs reversed. Uniqueness claims must name the objective and distinguish matrices from their factorizations.