9-Gram-Schmidt-Process.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "db2fa324-ee16-4eb9-bbe5-b2e3521bbd00",
   "metadata": {},
   "source": [
    "# Gram-Schmidt orthogonalization\n",
    "\n",
    "Recall when $\\mathcal{U} = \\{v_{1},v_{2},\\dots,v_{n}\\}$ is a basis of a vector space $V$, then we can construct an *orthogonal basis* out of $\\mathcal{U}$ using the following Gram-Schmidt process:\n",
    "$$\n",
    "\\begin{align*}\n",
    "v_{1}' &= v_{1} \\\\\n",
    "v_{2}' &= v_{2} - proj_{v_{1}'} (v_{2}) \\\\\n",
    "v_{3}' &= v_{3} - proj_{v_{1}'} (v_{3}) - proj_{v_{2}'} (v_{3}) \\\\\n",
    "& \\vdots \\\\\n",
    "v_{i}' &= v_{i} - proj_{v_{1}'} (v_{i}) - \\dots - proj_{v_{i-1}'} (v_{i}) \\\\\n",
    "& \\vdots \\\\\n",
    "v_{n}' &= v_{n} - proj_{v_{1}'} (v_{n}) - \\dots - proj_{v_{n-1}'} (v_{n}).\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a4973efb-2664-430d-ae7b-1b39d8a129d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "96a85364-0652-4a41-acdc-3ab2d672b744",
   "metadata": {},
   "outputs": [],
   "source": [
    "def proj(x,y):\n",
    "    p = (x.T@y)/(y.T@y) * y\n",
    "    return p\n",
    "\n",
    "def orthog(U):\n",
    "    \"\"\"\n",
    "    The input U is a matrix of shape (m,n), whose columns constitute a basis of a vector space.\n",
    "    \"\"\"\n",
    "    n = np.shape(U)[1]\n",
    "    Vp = np.zeros(np.shape(U))\n",
    "    for i in range(n):\n",
    "        u_i = U[:,i].copy()\n",
    "        Vp[:,i] = U[:,i]\n",
    "        for j in range(i):\n",
    "            p_j = proj(u_i,Vp[:,j])\n",
    "            Vp[:,i] -= p_j\n",
    "    return Vp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "97536eda-e003-4e34-9340-720f26184b3a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The orthogonal basis constructed using the Gram-Schmidt process is\n",
      "U' = \n",
      "[[ 1.   0.8]\n",
      " [ 2.  -0.4]].\n"
     ]
    }
   ],
   "source": [
    "U = np.array([[1, 1], [2, 0]])\n",
    "Up = orthog(U)\n",
    "print(f\"The orthogonal basis constructed using the Gram-Schmidt process is\\nU' = \\n{Up}.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e95eb606-836b-4815-9f41-0c366b0c919d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[5. , 0. ],\n",
       "       [0. , 0.8]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# double check that U' is orthogonal by testing if U'@U is diagonal.\n",
    "Up.T@Up"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d07b58c2-23d4-4e3b-9d97-b05bcff9a4ef",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "np.int64(4)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U = np.array([[1, 1, 0, 0], [0, 1, 1, 0], [1, 0, 0, 0], [0, 0, 1, 1]])\n",
    "np.linalg.matrix_rank(U)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "705534dd-2522-4b8a-ab16-588ad83fc078",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The orthogonal basis constructed using the Gram-Schmidt process is\n",
      "U' = \n",
      "[[ 1.          0.5        -0.33333333  0.25      ]\n",
      " [ 0.          1.          0.33333333 -0.25      ]\n",
      " [ 1.         -0.5         0.33333333 -0.25      ]\n",
      " [ 0.          0.          1.          0.25      ]].\n"
     ]
    }
   ],
   "source": [
    "Up = orthog(U)\n",
    "print(f\"The orthogonal basis constructed using the Gram-Schmidt process is\\nU' = \\n{Up}.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d27aab21-ef64-46fa-9eb3-702a00feb880",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 2.00000000e+00,  0.00000000e+00,  0.00000000e+00,\n",
       "         0.00000000e+00],\n",
       "       [ 0.00000000e+00,  1.50000000e+00,  5.55111512e-17,\n",
       "        -5.55111512e-17],\n",
       "       [ 0.00000000e+00,  5.55111512e-17,  1.33333333e+00,\n",
       "         1.38777878e-16],\n",
       "       [ 0.00000000e+00, -5.55111512e-17,  1.38777878e-16,\n",
       "         2.50000000e-01]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Up.T@Up"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}