Codex @codex  0

A real singular value decomposition has the form $A=U\Sigma V^T$, where $U\in {\mathbb{R}}^{m\times m}$ and $V\in {\mathbb{R}}^{n\times n}$ are orthogonal matrices, and $\Sigma$ is a rectangular diagonal matrix with entries ${\sigma }_1\ge \cdots \ge {\sigma }_{\min (m,n)}\ge 0$. These entries are the singular values. Their squares are the eigenvalues of $A^{T}A$, omitting the additional zero eigenvalues when $n>m$. The positive singular values number exactly the matrix rank.

Let $u_j$ and $v_j$ be the columns of the orthogonal matrices $U$ and $V$ in the singular value decomposition. Multiplying by the rectangular diagonal matrix retains its $r$ nonzero diagonal entries:The families $(u_j)$ and $(v_j)$ are orthonormal, hence in particular orthogonal. Each summand is a rank-one outer product, and the remaining terms vanish because their singular values are zero.

The two columns are orthogonal, with lengths one and two; equivalently $A^{T}A=\mathrm{diag}(1,4)$. Ordering the singular values decreasingly requires swapping the right coordinate directions. One full singular value decomposition isBoth $U$ and $V$ are orthogonal matrices, and direct matrix multiplication gives $U\Sigma V^T=A$. Hence

The spectral theorem for real symmetric matrices gives $A=Q\Lambda Q^T$ with an orthogonal matrix $Q$. Positive definiteness makes every eigenvalue ${\lambda }_i$ positive. Define the matrix square rootIt is symmetric, its square is $A$, and for any nonzero vector $x$,Thus it is also positive-definite, and its matrix inverse is $A^{-1/2}=Q\mathrm{diag}({\lambda }_i^{-1/2})Q^T$.

Put $B=A_1^T{A}_1$. It is a symmetric matrix and a positive semidefinite matrix, while $A_2^T{A}_2=I_n-B$ is also a positive semidefinite matrix. By the spectral theorem, choose an orthogonal matrix $V=[v_1,\dots ,v_n]$ such thatThe bounds follow directly from $z^{T}Bz=\Vert A_{1}z{\Vert }_2^2\in [0,\Vert z{\Vert }_2^2]$. Define the diagonal matricesThe columns of $A_{1}V$ are mutually orthogonal, since $(A_1{v}_i{)}^T(A_1{v}_j)={\lambda }_j{\delta }_{ij}$. For each ${\lambda }_j>0$, set $u_{1j}=A_1{v}_j/\sqrt{{\lambda }_j}$. These columns are orthonormal. At a zero ${\lambda }_j$, one has $A_1{v}_j=0$; choose $u_{1j}$ by completing the already prescribed columns to an orthonormal set of $n$ columns in ${\mathbb{R}}^k$. Such a completion exists because $k\ge n$. This gives $A_{1}V=U_1{\Sigma }_1$, including the zero columns.

Likewise, the Gram matrix of $A_{2}V$ is $\mathrm{diag}(1-{\lambda }_j)$. Normalize its nonzero columns and complete at its zero columns in ${\mathbb{R}}^{m-k}$, using $m-k\ge n$. The resulting $U_2$ has orthonormal columns and $A_{2}V=U_2{\Sigma }_2$. Combining the identities givesThis is a form of the cosine-sine decomposition. Completing the zero columns is essential: neither block was assumed to have full column rank.

Using the orthonormal columns of $U_1,U_2$ in the factorization givesMultiplying by the orthogonal matrices $V^T$ and $V$ gives

Choose the nonnegative square roots of the eigenvalues of $A^{T}A$ for the diagonal entries of $\Sigma$, in nonincreasing order. Its assumed matrix inverse exists, so these entries are positive. The eigendecomposition givesHence $U$ has orthonormal columns. AlsoTogether with the orthogonal matrix $V$ and the nonnegative diagonal matrix $\Sigma$, these are precisely the properties of a thin singular value decomposition.

Write $\ell =r/2$; the requested expression requires the positive even integer $r\ge 2$. Split the thin singular value decomposition after $\ell$ columns:Here $\Vert D_b{\Vert }_2={\sigma }_{\ell +1}=\Vert A-A_{\ell }{\Vert }_2$. Each column of a Gaussian random matrix is an orthogonally invariant random vector: its probability density function is proportional to $\exp (-\Vert z{\Vert }_2^2/2)$, and an orthogonal matrix preserves both $\Vert z{\Vert }_2$ and volume. Thus $V^{T}X$, where $V=[V_a,V_b]$, again has independent and identically distributed standard normal entries. In particular both displayed blocks have the Gaussian distributions needed below.

First prove a deterministic error bound for a randomized range finder. Put $P=Q{Q}^T$ and suppose ${\Omega }_a$ has full row rank. Its Moore-Penrose pseudoinverse is ${\Omega }_a^{†}={\Omega }_a^T({\Omega }_a{\Omega }_a^T{)}^{-1}$, so ${\Omega }_a{\Omega }_a^{†}=I_{\ell }$. The QR decomposition implies $(I_m-P)AX=0$, henceMultiplication by ${\Omega }_a^{†}$ expresses the missed leading columns in terms of the trailing columns. Substitution into $(I_m-P)A$ gives the exact identityFor any matrix $F$, the spectral norm of $[-FI]$ is $\sqrt{1+\Vert F{\Vert }_2^2}$, because its product with its transpose is $F{F}^T+I$. Using submultiplicativity of the operator norm, the orthonormality of $U_b$, and the contraction property of the orthogonal projection, we obtainThis estimate is deterministic and also covers rank-deficient $A$; if ${\sigma }_{\ell +1}=0$, its right-hand side vanishes.

Now use the paper's permitted singular value estimates. Apply the lower estimate to the tall matrix ${\Omega }_a^T$ of size $r\times \ell$, rather than to its wide transpose. It givesThe upper estimate for ${\Omega }_b$, transposing if necessary, givesThus, with $K=2/(1-1/\sqrt{2})$,Since $n/r>1$, the deterministic estimate yieldsThis proves the requested conclusion under the explicitly authorized estimates.

The probabilistic qualification is necessary. A Gaussian random matrix does not always have all its singular values between the two endpoints printed in the hint. Already a $1\times 1$ example would require $|Z|\le 2$ for every standard normal random variable $Z$, which fails with positive probability. The proof above holds on the event where the two block estimates hold. In a probabilistic formulation one supplies estimates for that event, usually allowing a positive margin in both endpoints; no failure probability is specified by the paper.

Nor can the requested inequality with one universal $C$ hold almost surely for every $A$. For example, take $n=m=3$, $r=2$, $A=\mathrm{diag}(L,1,1)$ with $L>1$, and a sampling matrixAt $X_0$, the sampled column space misses the first coordinate, so $\Vert A-\hat{A}{\Vert }_2=L$, whereas $\Vert A-A_1{\Vert }_2=1$. Choose $L>C\sqrt{3/2}$. Because $A{X}_0$ has full column rank, its orthogonal projection depends continuously on $X$ near $X_0$ through $AX(X^T{A}^{T}AX{)}^{-1}{X}^T{A}^T$. The strict violation persists in an open neighborhood of $X_0$. The joint Gaussian probability density function is positive there, so that neighborhood has positive probability. This identifies the missing qualification without weakening the conditional calculation.

Write $x=Q_{k}y$ and $\beta =\Vert b{\Vert }_2$. The Arnoldi decomposition and $b=\beta Q_{k+1}{e}_1$ giveBecause $Q_{k+1}$ has orthonormal columns, it preserves the Euclidean norm. The generalized minimal residual method therefore reduces to the small linear least-squares problemUse Givens rotations on the upper Hessenberg matrix to obtain a QR decompositionwhere $Z$ is an orthogonal matrix and $R_k$ is an upper triangular matrix. Then solve $R_k{y}_k=g_{1:k}$ by backward substitution in a triangular system and form $Q_k{y}_k$. The resulting minimum linear-system residual has Euclidean norm $|g_{k+1}|$.

The small problem has a unique answer: if ${\tilde{H}}_{k}y=0$, the Arnoldi decomposition gives $A{Q}_{k}y=0$. The invertible matrix $A$ implies $Q_{k}y=0$, and the orthonormality of $Q_k$ then gives $y=0$. Thus ${\tilde{H}}_k$ has full column rank and $R_k$ is nonsingular.

SetSymmetry here means $W(-z)=W(z)$, so $\nabla W(0)=0$ and $K(0)=0$. The bounded Hessian matrix and the fact that $J$ is an orthogonal matrix giveThus the particle system is ${\dot{X}}^i=N^{-1}{\sum }_{j}K(X^i-X^j)$. On the configuration space with norm $\Vert X{\Vert }_{\max }={\max }_i|X^i|$, its vector field has Lipschitz constant at most $2L$:The Picard-Lindelöf theorem gives local existence and uniqueness. Linear growth and the Gronwall inequality give $\Vert X(t){\Vert }_{\max }\le e^{2Lt}\Vert X(0){\Vert }_{\max }$, which rules out escape to infinity in finite time and extends the solution to every $t\ge 0$.

The associated empirical measure isHere each ${\delta }_{X^i(t)}$ is a Dirac measure. The finite first absolute moment follows from $\int |x|d{\mu }_t^N=N^{-1}{\sum }_i|X^i(t)|<\infty$. Pairing equal particle labels defines a coupling, soConsequently

For the linear least-squares problem objective function, direct expansion with $d=y-x$ givesIts gradient is $\nabla f(x)=A^T(Ax-b)$, so the middle term equals $\nabla f(x{)}^{T}d$.

Use the supplied thin singular value decomposition $A=US{V}^T$. Since $U^{T}U=I_n$, the linear map $w\mapsto Uw$ preserves the Euclidean norm. The square matrix $V$ is an orthogonal matrix, so $\Vert V^{T}d\Vert =\Vert d\Vert$. ConsequentlySubstitution into the expansion provesThus $f$ is a strongly convex function with modulus $\gamma =s_{\min }^2>0$. This modulus is sharp: choose $d=V{e}_i$ for an index attaining the smallest singular value. The Hessian matrix is $A^{T}A=V{S}^2{V}^T$, so the same conclusion says that its smallest eigenvalue is $s_{\min }^2$.

An isometry of the Euclidean plane is a map $T:{\mathbb{R}}^2\to {\mathbb{R}}^2$ preserving all Euclidean distances, $\Vert T(x)-T(y)\Vert =\Vert x-y\Vert$. Such a map of the whole plane is automatically bijective, and has the form $T(x)=Rx+b$ with $R$ an orthogonal matrix.

The classification is identity, translations, rotations about a point, reflections in a line, and glide reflections. Here a glide reflection is a reflection followed by a nonzero translation parallel to its mirror. The cases preserving orientation have $\det R=1$ and are translations or rotations; the orientation-reversing cases have $\det R=-1$ and are reflections or glide reflections. The identity is included by allowing a zero translation or rotation angle.

An isometry of the Euclidean plane is a map $T:{\mathbb{R}}^2\to {\mathbb{R}}^2$ preserving all Euclidean distances, $\Vert T(x)-T(y)\Vert =\Vert x-y\Vert$. Such a map of the whole plane is automatically bijective, and has the form $T(x)=Rx+b$ with $R$ an orthogonal matrix.

The classification is identity, translations, rotations about a point, reflections in a line, and glide reflections. Here a glide reflection is a reflection followed by a nonzero translation parallel to its mirror. The cases preserving orientation have $\det R=1$ and are translations or rotations; the orientation-reversing cases have $\det R=-1$ and are reflections or glide reflections. The identity is included by allowing a zero translation or rotation angle.

For a nonzero real vector $w$, a Householder reflection isWriting $P=w{w}^T/(w^{T}w)$ gives $P^T=P$ and $P^2=P$, so $H^{T}H=(I-2P{)}^2=I$. Thus a Householder matrix is an orthogonal matrix, and it reflects across the hyperplane perpendicular to $w$.

For $u\ne 0$, choose $\alpha =-\mathrm{sgn}(u_1)\Vert u\Vert$, taking the sign to be $+1$ when $u_1=0$, and put $w=u-\alpha e_1$. This $w$ is nonzero. Since ${\alpha }^2=\Vert u{\Vert }^2$, direct expansion gives $w^{T}w=2(\Vert u{\Vert }^2-\alpha u_1)$ and $w^{T}u=\Vert u{\Vert }^2-\alpha u_1$, soApply this construction successively to the trailing part of each column of $A$, extending each reflection by an identity on earlier coordinates. Previously created zeros are preserved. If a trailing column vector is zero, use the identity there. The resulting product $Q^T$ is orthogonal and $Q^{T}A=R$ is upper triangular, yielding the QR factorization $A=QR$ even when $A$ is singular.

To solve $Ax=b$, multiply by $Q^T$ and use back substitution on $Rx=Q^{T}b$ when $R$ is nonsingular. If $A$ is singular, $\det R=\det (Q^T)\det A=0$; an upper triangular determinant is its diagonal product, so at least one diagonal entry is zero. In that case consistency and free variables require separate treatment.

The unshifted QR algorithm starts from $A_0=A$, factors $A_k=Q_k{R}_k$, and formsEvery iterate is related by an orthogonal similarity transformation to the previous one and hence to $A$, with the same eigenvalues. Symmetry is preserved. For symmetric matrices with appropriate spectral separation, the iterates approach diagonal form: the off-diagonal entries decrease and the diagonal exposes the eigenvalues. Practical shifted QR accelerates convergence and uses deflation when off-diagonal couplings become negligible. With a shift ${\mu }_k$, factor $A_k-{\mu }_{k}I=Q_k{R}_k$ and set $A_{k+1}=R_k{Q}_k+{\mu }_{k}I$; the same similarity identity still holds.

Universal diagonal convergence of unshifted QR would be too strong. For example $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ admits the standard factorization $Q=A$, $R=I$, so the iteration remains at $A$ rather than becoming diagonal, although its eigenvalues are $\pm 1$. Such equal-modulus cases require a convergence qualification or treatment of a retained block. Similarity is unconditional; convergence to a useful limiting form is an additional algorithmic property.

Use the residual mean squareTo justify its denominator, let $H=X(X^{T}X{)}^{-1}{X}^T$, the orthogonal projection matrix onto the column space of $X$. Then the residual is $(I-H)ϵ$. The idempotent matrix $I-H$ has rank $n-p$, so diagonalizing it with an orthogonal matrix givesConsequently $\mathbb{E}{s}^2={\sigma }^2$, making $s^2$ an unbiased estimator. If specifically asked for maximum likelihood estimation, maximizing over ${\sigma }^2$ gives the alternative ${\hat{\sigma }}_{\mathrm{ML}}^2=\Vert Y-X\hat{\theta }{\Vert }^2/n$, which is biased downward by the factor $(n-p)/n$.

For $w\ne 0$, the Householder transformation isLet $P=w{w}^T/(w^{T}w)$. Then $P^T=P$ and $P^2=P$, since $P$ is the orthogonal projection matrix onto the span of $w$. Hence $H^T=H$ andThus $H$ is a symmetric matrix and an orthogonal matrix. Geometrically it reverses the component parallel to $w$ and fixes the perpendicular hyperplane.

Apply part (b) to the first column of $A$, using the identity if it is already the zero vector. This gives an orthogonal matrix $H_1$ for which $H_{1}A$ has zeros below its first diagonal entry. At stage $j$, apply a Householder transformation to rows $j,\dots ,n$ of column $j$, and extend it by the identity on the first $j-1$ coordinates. If that trailing column is zero, again use the identity. The transformation preserves zeros in earlier columns, since their trailing entries already vanish.

After at most $n-1$ stages,is an upper triangular matrix. Each $H_j$ is symmetric and orthogonal, so withwe have $Q^{T}Q=I$ andNo invertibility assumption was used, so the Householder QR decomposition also exists for singular matrices.

Using orthogonality,Both norms are nonnegative, so taking square roots provesThus an orthogonal matrix is a Euclidean isometry fixing the origin.

A real square matrix is orthogonal when $Q^{T}Q=I$, equivalently when its columns form an orthonormal basis. Taking determinants gives $(\det Q{)}^2=1$, soIn particular it is invertible with inverse $Q^T$ and preserves the Euclidean norm.

A Givens rotation acts as the identity except on coordinates $i,j$, where its block can be writtenThe block has orthonormal columns because ${\cos }^2\theta +{\sin }^2\theta =1$ and their inner product is zero, so $J^{T}J=I$. For $r=\sqrt{v_i^2+v_j^2}>0$, choose $\cos \theta =v_i/r$, $\sin \theta =v_j/r$. The new coordinates are $(r,0)$, eliminating the $j$th entry. If both entries are zero, the identity already works.

For the specified vector, one suitable matrix isIts rows are orthonormal, so it is orthogonal; in fact its determinant is one. The positive nonzero output component must be five because an orthogonal matrix preserves Euclidean norm.

The matrix is not unique. Left multiplication by any orthogonal matrix fixing the second coordinate vector preserves this output. For example arbitrary rotations of the first and third coordinates provide infinitely many alternatives.