Projection onto a positive semidefinite trace ball Created 2026-09-24 Updated 2026-11-05
Let be a real symmetric matrix with eigenpairs , and take trace radius . Its Frobenius norm projection onto the positive semidefinite trace ball is obtained by thresholding its eigenvalues. If , the projection is zero. If , it is . Otherwise and
In this last case is unique: the left side is continuous, strictly decreasing while positive, starts above at zero and reaches zero at .
To prove the reduction, use an orthonormal eigenbasis of . Replacing a feasible matrix by its diagonal part in that basis preserves nonnegative diagonal entries and the trace, hence remains positive semidefinite, while deleting off-diagonal entries decreases the squared Frobenius distance. The problem becomes projection of onto . Its multiplier equations give with the stated inactive-constraint case.
For and , the threshold gives . At radius zero the threshold itself need not be unique, although the projected matrix is; this is why that case is stated separately.
QR decomposition by Givens rotations Created 2026-09-24 Updated 2026-10-14
Successive Givens rotations eliminate entries below the diagonal of a matrix. For an matrix with , process columns ; within column , rotate rows for each whose entry needs elimination. Apply each Givens row-pair update to columns . Both rows are zero in earlier columns, so these operations preserve earlier eliminations. No assumption of full column rank is needed to perform the eliminations.
For a concrete example, take
First use , then :
The entry in position was already zero, so its elimination was skipped. The second Givens rotation combines the remaining pair in column two. This yields the full QR decomposition
The first two columns of and first two rows of give the reduced QR decomposition. Direct multiplication verifies both and . For these displayed factors evaluated in binary64 floating-point arithmetic, the Frobenius norms and are both below ; these measure reconstruction and loss of orthogonality separately.
Figure 1.
Two local Givens row-pair updates turn a matrix into the rectangular of a QR decomposition
. Details.
More generally, if the chronological rotations are , then
Each factor is an orthogonal matrix, so is too. For a rectangular matrix, has zeros below its diagonal; its leading block is an upper triangular matrix. With full column rank, retaining the first columns of gives orthonormal columns. To impose a positive diagonal when necessary, flip matching columns of and rows of , preserving their product.
For a linear least-squares problem, apply the same chronological Givens rotations to the right-hand side , obtaining , without explicitly constructing . Since the Euclidean norm is preserved, solve the leading upper triangular matrix system by back substitution when has full column rank; the remaining entries of give the minimum residual norm. In the example, gives , , and minimum residual Euclidean norm .
The locality is useful for a sparse matrix or an existing QR decomposition needing an extra row: only two rows change at each step, and the new row can be eliminated against the stored upper triangular matrix. For an factor, this extra-row procedure takes rotations and arithmetic operations. Locality does not guarantee preservation of sparsity: mixing rows can create nonzeros wherever either row had one. For a fully populated input, the straightforward elimination uses rotations, each touching columns, giving work. Storage layout, zero patterns and implementation affect speed; this count alone establishes no universal advantage over other QR decomposition algorithms.
The Euclidean norm preservation explains the appeal for numerical stability: exact rotations do not amplify a perturbation's length. Rounded coefficients and Givens row-pair updates still introduce roundoff error. Small reconstruction and orthogonality residuals check the computed factors, while the condition number of the original problem still controls how accurately a linear least-squares problem determines its solution.
Singular value decomposition Created 2026-09-24 Updated 2026-10-14
The singular value decomposition separates any matrix into input directions, stretching factors, and output directions. Every complex matrix admits
Here are unitary matrices, is the conjugate transpose, and is a rectangular diagonal matrix. Its diagonal entries are the singular values, ordered . We use the conventional letters: contains the right singular vectors , while contains the left singular vectors . Writing instead merely swaps these two matrix names; it requires swapping their roles consistently. For real matrices, choose orthogonal matrices and replace the conjugate transpose with the transpose.[ref]
Reading from right to left, expresses the input in an orthonormal basis, stretches or annihilates those coordinates, and assembles the output in another orthonormal basis. Unlike matrix similarity, the input and output bases can differ, and even have different sizes. A matrix has full factors of sizes , , and . If its matrix rank is , one can retain only the active columns, giving sizes , , and for ; the full additionally describes an unused output direction.
For a fully computed nonsymmetric example, take
Multiplication gives . The right singular vectors are and ; their images are and . Thus, parametrizing the unit circle by gives . Its image is the ellipse . The two singular values are its semiaxis lengths, and the left singular vectors point along its axes. The singular value decomposition finds precisely the perpendicular input directions whose images stay perpendicular.
Figure 1.
The unit circle becomes an ellipse: and
. Details.
For compression, write the matrix as a sum of outer products and retain the largest terms:
where is the matrix rank. Among all matrices of matrix rank at most , minimizes the Frobenius norm error; this is the Eckart-Young-Mirsky theorem. The operator norm error is for . These statements concern specified norms, rather than guaranteeing that discarded details are visually or scientifically unimportant.[ref]
Consider an brightness matrix , with
and , . The broad bright patch and alternating checkerboard have orthogonal row and column directions: . Their singular values are and . This low-rank approximation keeps the first outer product, giving , with Frobenius norm error and relative error . For example, becomes , and becomes : every entry changes by in magnitude. The discarded pattern is small but entirely lost.
Figure 2.
An matrix, its rank-one approximation, and the discarded checkerboard
. Details.
For this illustrative image compression, storing one normalized left singular vector, one normalized right singular vector, and one singular value requires scalars instead of . This counts scalars at equal precision, before storage overhead. In general, scalars beat only for sufficiently small , and small error requires a small discarded sum of squared singular values. The usefulness comes from measuring the tradeoff before throwing information away.[ref]
On a finite-dimensional positive inner-product space, a skew-adjoint nilpotent operator is zero. In an orthonormal basis, , since a nilpotent matrix has zero trace and so does its square. The Frobenius norm therefore vanishes. In particular, a nonzero nilpotent adjoint map rules out a compact Lie algebra.