Gram-Schmidt Orthonormalization

mediumFREEVectorsCV: Mathematical Foundations

Implement the Gram-Schmidt process to orthonormalize a set of vectors using NumPy.

Given a list of linearly independent vectors, produce an orthonormal basis where:

Each output vector is unit length (norm = 1)
All output vectors are mutually orthogonal (dot product = 0)

The Gram-Schmidt process:

Start with the first vector, normalize it: $\mathbf{u}_1 = \frac{\mathbf{v}_1}{\|\mathbf{v}_1\|}$
For each subsequent vector $\mathbf{v}_k$ $v_{k}$ :
- Subtract projections onto all previous orthonormal vectors
- $\mathbf{w}_k = \mathbf{v}_k - \sum_{j=1}^{k-1} (\mathbf{v}_k \cdot \mathbf{u}_j) \mathbf{u}_j$
- Normalize: $\mathbf{u}_k = \frac{\mathbf{w}_k}{\|\mathbf{w}_k\|}$

This algorithm is fundamental in CV for creating orthonormal bases in feature spaces.

Example

Input

vectors = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]

Output

[[0.7071, 0.7071, 0.0], [0.4082, -0.4082, 0.8165], [-0.5774, 0.5774, 0.5774]]

Reasoning

Input: three linearly independent vectors in $\mathbb{R}^3$ : $\mathbf{v}_1=[1,1,0]$ , $\mathbf{v}_2=[1,0,1]$ , $\mathbf{v}_3=[0,1,1]$ . The output is three unit vectors spanning the same space, in the same order.
First direction: $\|\mathbf{v}_1\|=\sqrt{2}$ , so $\mathbf{u}_1=\frac{1}{\sqrt2}[1,1,0]\approx[0.7071, 0.7071, 0]$ .
Second: $\mathbf{v}_2\cdot\mathbf{u}_1=\frac{1}{\sqrt2}$ , so the part of $\mathbf{v}_2$ along $\mathbf{u}_1$ is $\frac12[1,1,0]$ . Removing it leaves $\mathbf{w}_2=[0.5,-0.5,1]$ with $\|\mathbf{w}_2\|=\sqrt{1.5}\approx1.2247$ , giving $\mathbf{u}_2=\frac{1}{\sqrt6}[1,-1,2]\approx[0.4082,-0.4082,0.8165]$ .
Third: $\mathbf{v}_3\cdot\mathbf{u}_1=\frac{1}{\sqrt2}$ and $\mathbf{v}_3\cdot\mathbf{u}_2=\frac{1}{\sqrt6}$ . Subtracting $\frac12[1,1,0]$ and $\frac16[1,-1,2]$ leaves $\mathbf{w}_3=[-\frac23,\frac23,\frac23]$ , norm $\frac{2}{\sqrt3}\approx1.1547$ , so $\mathbf{u}_3\approx[-0.5774,0.5774,0.5774]$ .
Notice: every pair now has dot product $0$ (e.g. $0.7071\cdot0.4082-0.7071\cdot0.4082+0=0$ ), and the first output always points along $\mathbf{v}_1$ , so reordering the inputs changes the basis. All components are rounded to 4 decimal places.

Constraints

Input: List of n vectors, each of dimension d
Vectors are linearly independent
Return: List of n orthonormal vectors (as lists)
Round each component to 4 decimal places

Learn this in

Linear AlgebraFoundations

More from CV: Mathematical Foundations

Adam Optimizer Stephard Power Iteration for Dominant Eigenvectorhard SVD Image Compressionhard Batch Affine Transform with PyTorchmedium Covariance Matrix from Image Patcheshard

Concept primer

Gram-Schmidt Orthonormalization: Background & Implementation Guide

Background Knowledge

The Gram-Schmidt process is a fundamental algorithm for converting a set of linearly independent vectors into an orthonormal basis—a set of vectors that are mutually perpendicular and each have unit length. This is essential in computer vision and machine learning because orthonormal bases simplify many computations: dot products become projections, matrix operations become more numerically stable, and geometric interpretations become clearer.

The key insight is that any vector can be decomposed into two components: one parallel to a given direction and one perpendicular to it. The Gram-Schmidt process iteratively removes the "parallel" components (projections onto previously computed orthonormal vectors) from each new vector, leaving only the perpendicular part, which is then normalized. Mathematically, the projection of vector $\mathbf{v}$ onto a unit vector $\mathbf{u}$ is $($ \mathbf{v} $\cdot$ \mathbf{u} $)\mathbf{u}$ , and subtracting this from $\mathbf{v}$ gives the perpendicular component.

This process is widely used in QR decomposition, solving least-squares problems, and constructing orthonormal feature spaces in computer vision applications.

Algorithm/Approach

The Gram-Schmidt process follows a sequential, iterative pattern:

Normalize the first vector to create the first orthonormal basis vector
For each subsequent vector, apply a two-step procedure:

Orthogonalize: Remove all components parallel to previously computed orthonormal vectors
Normalize: Scale the result to unit length

This greedy approach works because once you have orthonormal vectors $\mathbf{u}_1, \ldots,$ \mathbf{u} $_{k-1}$ , the subspace orthogonal to all of them is well-defined, and any vector in that subspace can be made orthonormal by normalization.

Step-by-Step Strategy

Step 1: Input Validation

Verify that input vectors are linearly independent (no zero vectors after orthogonalization)
Ensure vectors are stored in a format compatible with NumPy operations (e.g., as rows or columns in a matrix)

Step 2: Initialize the Output

Create a container (list or array) to store orthonormal vectors as you compute them

Step 3: Process the First Vector

Compute its norm using np.linalg.norm()
Divide by the norm to normalize
Store as the first orthonormal vector

Step 4: Iteratively Process Remaining Vectors

For each vector $\mathbf{v}_k$ :
Initialize $\mathbf{w}_k =$ \mathbf{v} $_k$ (a copy to avoid modifying the original)
Loop through all previously computed orthonormal vectors $\mathbf{u}_j$ :
Compute the projection: $\text{proj} = ($ \mathbf{v} $_k \cdot$ \mathbf{u} $_j)$
Subtract: $\mathbf{w}_k =$ \mathbf{w} $_k -$ \text{proj} $\cdot$ \mathbf{u} $_j$
Normalize $\mathbf{w}_k$ and store as $\mathbf{u}_k$

Step 5: Return the Result

Combine all orthonormal vectors into the desired output format

Common Pitfalls

Numerical Instability: The classical Gram-Schmidt process can accumulate floating-point errors, especially with many vectors or nearly parallel input vectors. The computed vectors may lose orthogonality. Consider using the modified Gram-Schmidt variant, which reorthogonalizes by processing projections differently.

Zero Vectors After Orthogonalization: If a vector becomes (nearly) zero after subtracting projections, it indicates linear dependence among the input vectors. You must handle this gracefully—either skip the vector or raise an error.

In-Place Modifications: Avoid modifying input vectors directly. Always work with copies to preserve the original data.

Norm Computation: Use np.linalg.norm() rather than manual calculations for numerical stability. Be aware that very small norms (near machine epsilon) indicate numerical issues.

Dot Product Order: Ensure you're computing dot products correctly—the order matters for readability and debugging, though mathematically $\mathbf{a} \cdot$ \mathbf{b} $=$ \mathbf{b} $\cdot \mathbf{a}$ .

Time & Space Complexity

Time Complexity: $O(n \cdot m^2)$ , where $n$ is the dimension of each vector and $m$ is the number of vectors. For each of the $m$ vectors, you perform $O(m)$ dot products and vector operations, each costing $O(n)$ .

Space Complexity: $O(n \cdot m)$ for storing the input vectors and output orthonormal basis. If you process vectors sequentially and only keep the current and previous vectors in memory, you can reduce this to $O(n)$ , but typically you'll store all results.

Practical Note: The modified Gram-Schmidt variant has the same asymptotic complexity but better numerical properties, making it preferable for real-world applications.

solution.py

Python 3.13

Test results