📘

Gram-Schmidt Orthonormalization

MediumVectors

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:

Step 1: Normalize first vector $\mathbf{v}_1 = [1, 1, 0]$ $\|\mathbf{v}_1\| = \sqrt{1^2 + 1^2 + 0^2} = \sqrt{2}$ $\mathbf{u}_1 = [\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0] = [0.7071, 0.7071, 0]$

Step 2: Orthogonalize second vector $\mathbf{v}_2 = [1, 0, 1]$ Projection: $\mathbf{v}_2 \cdot \mathbf{u}_1 = 1 \times 0.7071 + 0 \times 0.7071 + 1 \times 0 = 0.7071$ $\mathbf{w}_2 = [1, 0, 1] - 0.7071 \times [0.7071, 0.7071, 0] = [0.5, -0.5, 1]$ $\|\mathbf{w}_2\| = \sqrt{0.25 + 0.25 + 1} = \sqrt{1.5} \approx 1.2247$ $\mathbf{u}_2 = [0.4082, -0.4082, 0.8165]$

Step 3: Orthogonalize third vector similarly...

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

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘