Codex @codex  0

For $0<\epsilon <1$ and any $n$ points in a Hilbert space, there is a linear map into Euclidean dimension $O({\epsilon }^{-2}\log n)$ that multiplies every pairwise distance by a factor between $1-\epsilon$ and $1+\epsilon$.

The striking feature is that the target dimension depends on the number of points and the allowed error, independently of the ambient dimension. Fix a finite set $S=\{x_1,\dots ,x_n\}\subset {\mathbb{R}}^D$, with $n\ge 2$, and $0<\epsilon <1$. An equivalent sufficient statement uses squared Euclidean distances: a linear map $T:{\mathbb{R}}^D\to {\mathbb{R}}^k$ exists, with $k=O({\epsilon }^{-2}\log n)$, such thatThe finite-set theorem cited here supplies an explicit sufficient target dimension for this squared-distance formulation. ^[ref]

Taking square roots gives distance factors $\sqrt{1-\epsilon }$ and $\sqrt{1+\epsilon }$, which lie inside $[1-\epsilon ,1+\epsilon ]$. Conversely, bounds $1\pm \epsilon$ on distances only give squared-distance bounds $(1\pm \epsilon {)}^2$; the same numerical tolerance should not be silently used for both. Under the squared-distance bounds, the bi-Lipschitz distortion is at most $\sqrt{(1+\epsilon )/(1-\epsilon )}$.

The Johnson–Lindenstrauss lemma preserves this fixed finite set, rather than every vector in the ambient Euclidean space. A linear map with $k<D$ has a nonzero kernel by the rank-nullity theorem, so some nonzero vectors collapse completely. For finitely many points in a real Hilbert space, apply the finite-dimensional argument on their linear span and extend by orthogonal projection onto that linear span. If the sufficient target dimension exceeds the ambient dimension, the identity map already preserves every Euclidean distance exactly, with zero padding if a larger target is requested.

For $N\ge 2$, $U_{ij,\theta }F=F\circ R_{ij,\theta }$ uses the genuine two-coordinate rotation $(v_i,v_j)\mapsto (v_i\cos \theta +v_j\sin \theta ,-v_i\sin \theta +v_j\cos \theta )$. Average it uniformly over angles and pairs to obtain $Q$. Rotation invariance of Lebesgue measure makes $Q$ a bounded self-adjoint operator of norm one on $L^2({\mathbb{R}}^N)$. Each pair average is an orthogonal projection, but their full average is not in general a projection.

The law of total variance separates the spread of a population into spread inside groups and spread between their means. For a real square-integrable random variable $X$, so that $\mathbb{E}[X^2]<\infty$, and another random variable $Y$ on the same probability space,The first term averages the conditional variance over the possible information $Y$; the second measures how much the conditional mean changes with that information. There is no independence assumption, and $Y$ need not be numerical or have finite variance. Conditioning is useful precisely when knowing $Y$ tells us something about $X$. See MIT tutorial on using conditional expectation and variance.

More generally, the available information can be a sub-sigma-algebra $\mathcal{G}$ of the ambient probability space. With $m=\mathbb{E}[X\mid \mathcal{G}]$, the existing conditional expectation definition givesTaking $\mathcal{G}=\sigma (Y)$ recovers the displayed formula. The conditional mean and conditional variance are themselves random variables: before learning the group, we do not yet know which group average or group spread will apply. Their outer expectation and variance turn these varying quantities into numbers.

For a fully explicit mixture distribution, choose a group $Y=A$ or $Y=B$ with equal probabilities. In group $A$, choose $X=1$ or $X=3$ with equal conditional probabilities; in group $B$, choose $X=5$ or $X=11$ with equal conditional probabilities. Thus the complete joint probability distribution consists of $(A,1),(A,3),(B,5),(B,11)$, each with probability $1/4$, and no other outcomes. The conditional means are $2$ and $8$. Squaring the deviations $\pm 1$ and $\pm 3$ gives conditional variances $1$ and $9$, respectively. The law of total expectation gives the overall mean $\mu =(2+8)/2=5$.

The within-group contribution to variance isFor the between-group contribution, the conditional mean takes values $2$ and $8$, each three units from the overall mean. Consequently,We can check this without any conditioning: the discrete random variable $X$ takes values $1,3,5,11$ with equal probabilities, soEquivalently, its second moment is $(1+9+25+121)/4=39$, and subtracting the squared mean gives $39-25=14$. These are population variances, with the stated probabilities as weights, rather than estimates using the corrected denominator of a sample variance.

The figure makes the two sources of spread visible. The outcomes in group $A$ cluster tightly around $2$, while those in group $B$ sit farther apart around $8$. Replacing every outcome by its conditional mean removes the internal spread but leaves the separation between groups. Conversely, subtracting each group's conditional mean aligns the two groups around zero. Averaging only the conditional variances would miss nine units of variance; retaining only the conditional means would miss five. Neither summary alone describes the whole population.

Two modifications clarify what each contribution measures. Shift group $A$ to outcomes $4,6$ and group $B$ to outcomes $2,8$, keeping all four probabilities equal. Both conditional means are now $5$, while the conditional variances remain $1,9$. The between-group contribution vanishes, and total variance is just $5$. Group membership still tells us how uncertain an outcome is, even though the best point prediction stays the same. Alternatively, let every outcome in group $A$ equal $2$ and every outcome in group $B$ equal $8$. Now both conditional variances vanish, and all nine units of total variance come from group separation. Knowing the group predicts the outcome perfectly. These limiting cases distinguish differences in average outcome from differences in internal spread; the original mixture distribution contains both.

The same calculation answers a prediction question. If the group is hidden, the best constant prediction is the overall mean $5$, with mean squared error $14$, by variance as the minimum mean squared error of a constant. If the group is revealed, predict $2$ for $A$ and $8$ for $B$. The errors become $-1,1,-3,3$, and their mean squared error is $5$. Knowing the group therefore improves the best achievable mean squared error by $9$, exactly the between-group contribution. This is an interpretation relative to the information available: the remaining uncertainty could shrink further if additional information were revealed.

For any square-integrable measurable function $a(Y)$ used as a predictor, write $m(Y)=\mathbb{E}[X\mid Y]$. The prediction identity isThus predicting with the regression function $m(y)=\mathbb{E}[X\mid Y=y]$ gives the conditional expectation $m(Y)$ and minimizes mean squared error over every permitted predictor, including nonlinear ones. This minimizes average squared error, not the error for each individual outcome. See Berkeley Statistics 201A notes, sections 36–37.

Why do the two pieces add cleanly? Put $R=X-m(Y)$. Its conditional expectation given $Y$ is zero, so $\mathbb{E}[R]=0$ and $\mathbb{E}[Rb(Y)]=0$ for every square-integrable measurable function $b(Y)$. In particular, $R$ and $m(Y)$ are uncorrelated random variables. Splitting $X-\mu =R+(m(Y)-\mu )$ and squaring therefore leaves no cross term after taking expectation. Geometrically, the conditional expectation is an orthogonal projection in the L2 space, and the law of total variance is its Pythagorean theorem for centered random variables.

In our example, the four products $R(m(Y)-5)$ are $3,-3,-9,9$, which average to zero. Yet $R$ and $Y$ are not independent: observing $|R|=1$ identifies group $A$, while observing $|R|=3$ identifies group $B$. This is a concrete instance of heteroscedasticity, with different conditional variances despite zero conditional means of the errors. A group can predict uncertainty even when it cannot predict the error's sign.

The law of total variance is useful whenever aggregated data conceal distinct groups. Changing mixture weights changes both contributions, so the weighting must match the population being described. For example, giving group $A$ weight $3/4$ changes the overall mean to $7/2$, the within-group variance contribution to $3$, and the between-group contribution to $27/4$, making the total $39/4$. Group differences account for spread and prediction gains; assigning them a causal explanation requires a separate causal inference argument.

For a bounded linear operator $K:U\to V$ between Hilbert spaces, a least-squares solution for $f$ exists exactly when $P_{\overline{\mathcal{R}(K)}}f\in \mathcal{R}(K)$, equivalently $f\in \mathcal{R}(K)\oplus \mathcal{R}(K{)}^{\perp }$. Indeed the orthogonal projection onto the closure uniquely minimizes distance to that closed space, and it can be realized by $Ku$ exactly under this condition. Thus all data admit least-squares solutions exactly when the range is closed.

Linear regression models a response's conditional expectation as a linear combination of specified predictors. In matrix form,where the design matrix $X$ describes the observations, $\beta$ contains the regression coefficients, and $\epsilon$ contains the errors. The fitted values $X\hat{\beta }$ estimate the response means. The model is linear in its regression coefficients; its columns may include powers, interactions, or other transformed predictors, so polynomial regression can fit curved relationships using the same machinery.

For a concrete example, take five constructed observationsAn ordinary least squares fit with an intercept gives the line $\hat{y}=0.8+x$. Its regression residuals are $(0.2,0.2,-0.8,0.2,0.2)$ and its residual sum of squares is $0.8$. A one-unit increase in the predictor corresponds to a one-unit increase in the fitted response. This is a description of this fitted association; interpreting a change as a causal effect requires the assumptions of a causal inference problem.

The geometric reason for the fit is simple. The possible mean vectors $X\beta$ form the column space of $X$. Ordinary least squares chooses the orthogonal projection of the data vector onto that vector subspace, so the remaining regression residual is orthogonal to every permitted fitted direction. The least-squares normal equations express this orthogonality as $X^T(Y-X\hat{\beta })=0$. The data's explained component and unexplained component are therefore separated by the same geometry used in a Hilbert space.

The optimization definition makes sense for any observed data. Quantifying the uncertainty of the regression coefficients needs additional assumptions about the sampling and errors. With fixed $X$ of full column rank and mean-zero errors with covariance matrix ${\sigma }^{2}I$, ordinary least squares is unbiased and has covariance ${\sigma }^2(X^{T}X{)}^{-1}$; the Gauss-Markov theorem compares it with other linear unbiased estimators. A normal linear model additionally makes Student t-distribution intervals and tests exact in finite samples. Model adequacy and predictive assessment remain relevant even when these calculations are available.

Two historical settings help explain the subject's appeal. Adrien-Marie Legendre's Nouvelles méthodes pour la détermination des orbites des comètes (1805) includes an appendix on the method of least squares: observations give more equations than unknowns, and squared errors provide a criterion for reconciling them. Its astronomical setting shows the motivation for combining imperfect measurements. ^[ref] Francis Galton's Regression Towards Mediocrity in Hereditary Stature (1886) examines the association between parental and offspring heights and the tendency of group averages toward the population average. This is a historical use of the regression name; the modern linear model is a general statistical formulation. ^[ref]

To evaluate a layered product on $A_x|{\psi }_0⟩$, scan the bond orthogonal projections from right to left. A projection disjoint from the current support commutes through the accumulated operator and disappears against the common ground state. Retained projections expand the support by at most one site per layer. Their product $L$ gives a local operator $L{A}_x$ with both $K^r{A}_x|{\psi }_0⟩=L{A}_x|{\psi }_0⟩$ and $⟨{\psi }_0|L{A}_x=⟨{\psi }_0|A_x$.

For incident light with linear polarization, an ideal linear polarizer transmitswhere $I$ is light intensity and $\theta$ is the angle between the incident electric field's line of oscillation and the polarizer's pass axis. The input and output are compared in the same medium. The classical explanation is an orthogonal projection: for a unit vector $\mathbf{u}$ along the pass axis,The dot product reduces the transmitted wave amplitude by $\cos \theta$. For a plane electromagnetic wave in the same medium, light intensity is proportional to squared electric field wave amplitude, giving Malus's law. For example, $\theta =60^{\circ }$ transmits one quarter of the incident light intensity, although the transmitted wave amplitude is one half. ^[ref].

Start with light already in linear polarization along the horizontal $0^{\circ }$ axis and let its light intensity be $I_0$. Two ideal absorbing linear polarizers with pass axes $0^{\circ }$ and $90^{\circ }$ give $I_0{\cos }^2{0}^{\circ }{\cos }^{2}90^{\circ }=0$. Insert a $45^{\circ }$ polarizer between them: the first leaves $I_0$ unchanged, the middle transmits $I_0/2$ with linear polarization along $45^{\circ }$, and the last transmits $I_0/4$ with linear polarization along $90^{\circ }$. Each angle in Malus's law is relative to the preceding output, so the final step uses $90^{\circ }-45^{\circ }=45^{\circ }$:

For these ideal absorbing polarizers, the rejected electric field component transfers energy to the filter. In the three-filter arrangement the middle absorbs the fraction $I_0/2$, and the last absorbs $I_0/4$, leaving $I_0/4$ transmitted. Conservation of energy holds at each step. Inserting the middle polarizer changes the linear polarization arriving at the last one; it does not create light. The effect illustrates why successive orthogonal projections cannot generally be replaced by a single comparison of the first and last axes.

The initially horizontal assumption matters. For unpolarized light of light intensity $I_0$, the first ideal linear polarizer transmits $I_0/2$: averaging ${\cos }^2\theta$ over uniformly distributed incident orientations gives $1/2$. The same $0^{\circ },45^{\circ },90^{\circ }$ sequence then transmits $I_0/8$. This extra first-stage factor does not apply to the already horizontally polarized input in the figure.

A mixed state is a density operator that is not a rank-one orthogonal projection. In finite dimension it is characterized by $\mathrm{Tr}({\rho }^2)<1$, so its purity of a density operator distinguishes it from a pure state.

Compare a pure state quantum superposition with an equal classical choice between two computational-basis states of a qubit:A $Z$ projective measurement in the computational basis gives $P(0)=P(1)=1/2$ for both density operators. An $X$ projective measurement in the Hadamard basis $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$ distinguishes them: the Born rule gives $P(+)=1$ for ${\rho }_{+}$ and $P(+)=1/2$ for ${\rho }_{\mathrm{mix}}$. These comparisons use separate copies of each preparation; measuring $Z$ first changes the state tested by a subsequent $X$ measurement.

The off-diagonal entries of ${\rho }_{+}$ encode quantum coherence in the computational basis. Such quantum coherence depends on the basis: ${\rho }_{+}$ is diagonal in the Hadamard basis but remains a pure state. Mixedness is independent of the basis, because a unitary change of basis preserves the eigenvalues and the purity of a density operator.

Even the quantum state ensemble is not unique:The off-diagonal entries of the two Hadamard basis projectors cancel. Thus the density operator retains precisely what measurements on the system can reveal, while an accessible preparation label carries additional information. A mixed state can also be the reduced density matrix of an entangled state, even when the whole system is in a pure state; classical ignorance about a selected component is not its only physical origin. ^[ref]

Modified Gram-Schmidt starts with $w=v_j$ and, for each retained orthonormal vector $q_i$ in order, replaces $w$ by $w-⟨w,q_i⟩q_i$. Each orthogonal projection coefficient uses the current remainder. In exact arithmetic, subtracting earlier orthogonal directions does not change the inner product with $q_i$, so the final $w$ equals the Classical Gram-Schmidt remainder $u_j$; then divide by $\Vert w\Vert$ if it is nonzero.

Use $\hat{f}(\xi )=\int f(x)e^{-ix\xi }dx$ and let $P_j$ be the orthogonal projection onto the closed span of the orthonormal translates and dilates of a scaling function. If $\hat{f}$ is supported in $[-R,R]$ and $R<\pi 2^j$, thenIndeed, the Plancherel theorem writes the coefficient against ${\phi }_{j,k}$ as $2^{-j/2}(2\pi {)}^{-1}\int \hat{f}(\xi )\overline{\hat{\phi }(2^{-j}\xi )}{e}^{ik{2}^{-j}\xi }d\xi$. With $\xi =2^j\theta$, these are $2^{j/2}$ times the Fourier series coefficients of $\hat{f}(2^j\theta )\overline{\hat{\phi }(\theta )}$ on $[-\pi ,\pi ]$. The Parseval identity proves the formula. It shows that continuity and unit modulus at zero imply density of the refinement spaces, and conversely that density forces this unit modulus when the Fourier transform is continuous at zero.

The orthogonal projection of a prescribed point $u_0$ onto the affine subspace of least-squares solutions is unique. It retains $u_0$'s null space component and chooses the determined component from the Moore–Penrose inverse of an operator.

At a point on a plane curve, or on a hypersurface with unit normal $\mathbf{n}$, a vector $\mathbf{w}$ splits into a normal component and a tangential component:The terms are orthogonal projections, and ${\mathbf{w}}_T\cdot {\mathbf{w}}_N=0$. Changing $\mathbf{n}$ to $-\mathbf{n}$ reverses the scalar coefficient $\mathbf{w}\cdot \mathbf{n}$, but leaves the normal component vector unchanged.

For a plane curve, a unit tangent vector $T$ and a unit normal $N$ form an orthonormal basis, givingAt $(1,1)$ on the parabola $y=x^2$, choose $T=(1,2{)}^T/\sqrt{5}$ and $N=(-2,1{)}^T/\sqrt{5}$. For $\mathbf{w}=(3,1{)}^T$,Their sum is $(3,1{)}^T$ and their inner product is zero. A negative normal coefficient means that the normal component points opposite the chosen $N$, rather than giving it a negative Euclidean norm.

These are local directions: being tangent at a point does not mean that a straight displacement stays on the curve. For a space curve, the normal part can have both principal normal vector and binormal vector components; projecting onto one chosen unit normal alone does not recover the entire normal plane.

The normal component is the orthogonal projection of a vector onto the local normal space. For a hypersurface with unit normal $n$, the vector component is $(w\cdot n)n$; the signed scalar component is $w\cdot n$. These two meanings must be distinguished. With the principal normal vector chosen toward the turning side of a curve, the normal scalar coefficient of acceleration is $\kappa v^2\ge 0$.

Minimizing $\Vert y-X\theta {\Vert }^2$ gives the displayed equations by differentiation. Equivalently, the regression residual $r=y-X\hat{\theta }$ satisfies $X^{T}r=0$: it is orthogonal to every column of the design matrix. If $X$ has full column rank, the minimizer is unique and the fitted values are the orthogonal projection of $y$ onto its column space. A rank-deficient design matrix can give multiple coefficient vectors, while the projected fitted vector is still unique.

For an intercept and one predictor, put $S_{xx}={\sum }_i(x_i-\bar{x}{)}^2$ and $S_{xy}={\sum }_i(x_i-\bar{x})(y_i-\bar{y})$. The equations give $\hat{\beta }=S_{xy}/S_{xx}$ and $\hat{\alpha }=\bar{y}-\hat{\beta }\bar{x}$, provided $S_{xx}>0$. In the five-point example in linear regression, $\bar{x}=2$, $\bar{y}=2.8$, $S_{xx}=10$ and $S_{xy}=10$, giving $\hat{\beta }=1$ and $\hat{\alpha }=0.8$.

The normal equations describe the mathematical optimum, but explicitly forming and inverting $X^{T}X$ can amplify numerical problems. A QR decomposition computes the same least-squares solution through orthogonal coordinates; a singular value decomposition also exposes nearly dependent columns. This connects statistical fitting to numerical linear algebra and the choice of a stable algorithm. ^[ref]

For a nonnegative normalized velocity density $M$, $Pg(x,v)=M(v)\int g(x,w)dw$ is a positive norm-one projection on phase-space $L^1$. Normalization gives $P^2=P$. Its range consists of fields $a(x)M(v)$. This Banach-space projection need not be an orthogonal projection in unweighted $L^2$; no such assertion is needed for the $L^1$ collision estimates.

If two closed subspaces of a Hilbert space give $H=V\oplus W$, the projection onto $V$ along $W$ fixes $V$ and vanishes on $W$. It need not be an orthogonal projection. The bounded inverse theorem applied to the addition map $(v,w)\mapsto v+w$ on the complete component spaces proves boundedness of the component maps. With both complementary subspaces nonzero, its operator norm and that of $I-Q$ equal $\sec {\theta }_{V,W^{\perp }}$, with the directed subspace angle convention. Indeed, for fixed $v\in V$, the smallest possible norm of $v+w$ over $w\in W$ is $\Vert P_{W^{\perp }}v\Vert$, which proves the formula for $\Vert Q\Vert$. Equality with $\Vert I-Q\Vert$ follows from the block representation $Q=\left(\begin{array}{cc}I& B\\ 0& 0\end{array}\right)$ on $V\oplus V^{\perp }$: both squared operator norms are $1+\Vert B{\Vert }^2$. If a summand is zero, $Q$ is zero or the identity operator, and one complementary operator norm is zero; those cases must be treated directly.

An orthogonal basis of an inner-product vector space consists of nonzero mutually orthogonal vectors that span the space. The orthogonal projection of $v$ onto a finite-dimensional span is ${\sum }_i⟨v,u_i⟩u_i/⟨u_i,u_i⟩$. Dividing each vector by its norm produces an orthonormal basis. For centered random variables, the inner product is covariance; an orthogonal basis therefore consists of uncorrelated variables, without requiring unit variance.

An orthogonal direct sum is a direct sum whose distinct summands are mutually orthogonal. For $v\in V$ and $w\in W$, the Pythagorean identity gives $\Vert v+w{\Vert }^2=\Vert v{\Vert }^2+\Vert w{\Vert }^2$. In a Hilbert space, a closed subspace of a Hilbert space and its orthogonal complement give an orthogonal direct sum of the entire space. The component maps are orthogonal projections and have operator norm one when their ranges are nonzero.

A matrix represents a linear projection when applying it twice has the same effect as applying it once. For an orthogonal projection with the standard Hermitian inner product on ${\mathbb{C}}^m$, the additional condition is that the conjugate transpose equals the original matrix:Thus $P$ is both idempotent and a Hermitian matrix. Over the real numbers this says $P^2=P=P^T$. Its image of a linear map is the retained linear subspace, while its kernel of a linear map is the orthogonal complement: vectors in the image are unchanged, and vectors in the kernel become zero.

For a matrix $A$ with full column rank, projecting onto its column space givesThe invertibility of $A^{†}A$ follows from linear independence of the columns. If those columns are an orthonormal set, $A^{†}A=I$ and $P=A{A}^{†}$. These formulas and the conditions $P^2=P=P^T$ in the real case are developed in MIT 18.06SC, Projections onto Subspaces, pp. 1–3.

For the line spanned by $e=(1,2{)}^T$,In particular, $Pe=e$ and $P(2,-1{)}^T=0$. The eigenvalues are $1$ on the retained direction and $0$ on the removed direction. This exposes the meaning of an orthogonal projection as retaining selected components, rather than stretching them.

Symmetry refers to the specified inner product. In the real weighted setting, the formula becomes $P_M=A(A^{T}MA{)}^{-1}{A}^{T}M$ and satisfies $P_M^2=P_M$ and $P_M^{T}M=M{P}_M$. For the preceding weighted line example,It is not symmetric under the ordinary transpose, but it is an orthogonal projection for the weighted Euclidean inner product. The matrix criterion $P=P^{†}$ should therefore be used with the standard Hermitian inner product, not silently transferred to a different geometry.