Skip to content

Instantly share code, notes, and snippets.

@vaibkumr

vaibkumr/Gram-Schmidt-Numpy-Python.ipynb

Created April 13, 2021 04:51
Show Gist options
  • Save vaibkumr/6f37755cd2954d06ca33b3a8b97f7898 to your computer and use it in GitHub Desktop.
Save vaibkumr/6f37755cd2954d06ca33b3a8b97f7898 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Gram-Schmidt-Numpy-Python.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"D = 5\n",
"n_vecs = 10\n",
"basis = [np.random.randn(D, ) for _ in range(n_vecs)]"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"#gram-shmidt-without-col-pivoting\n",
"def normalize(v):\n",
" return v/np.linalg.norm(v)\n",
"\n",
"orthonormal_basis = [normalize(basis[0])]\n",
"for b in basis[1:]:\n",
" for o_b in orthonormal_basis:\n",
" b = b - np.dot(b, o_b)*o_b\n",
" b = normalize(b)\n",
" orthonormal_basis.append(b) "
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[array([ 0.0019806 , 0.44848175, 0.89279469, 0.01347847, -0.0399521 ]),\n",
" array([-0.3882712 , -0.37593753, 0.20216096, -0.81672506, 0.00275065]),\n",
" array([ 0.77058636, -0.32425575, 0.14169771, -0.18368304, -0.49722949]),\n",
" array([ 0.07694287, 0.73743619, -0.37672516, -0.47026352, -0.29529314]),\n",
" array([ 0.49951777, 0.09263458, -0.00696472, -0.27909006, 0.81483806]),\n",
" array([-0.60347658, -0.15086914, 0.2098024 , -0.45260743, -0.60347658]),\n",
" array([-0.70737017, 0.50774284, 0.06523506, 0.23423442, 0.42743803]),\n",
" array([ 0.29168638, 0.84136557, -0.12495614, -0.23671389, -0.36793413]),\n",
" array([ 0.02142475, 0.04564354, 0.34682466, 0.78926703, -0.50421014]),\n",
" array([ 0.2233909 , 0.09724375, 0.90323084, -0.24759815, 0.25201063])]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"orthonormal_basis"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 1.00000000e+00 9.73206975e-17 -3.46944695e-18 1.04083409e-16\n",
" -1.11022302e-16 1.36462871e-01 2.70633972e-01 2.77863850e-01\n",
" 3.60938307e-01 8.37048599e-01]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 9.73206975e-17 1.00000000e+00 7.43762690e-17 -6.42931888e-17\n",
" 4.94396191e-17 7.01439691e-01 -9.31695264e-02 -2.62497461e-01\n",
" -6.01364392e-01 2.62216991e-01]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[-3.46944695e-18 7.43762690e-17 1.00000000e+00 -2.77555756e-17\n",
" -5.55111512e-17 -3.17944976e-03 -9.56044369e-01 1.60673947e-01\n",
" 1.56586878e-01 1.88768343e-01]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 1.04083409e-16 -6.42931888e-17 -2.77555756e-17 1.00000000e+00\n",
" -5.55111512e-17 1.54319830e-01 5.90537418e-02 9.09937062e-01\n",
" -3.17623588e-01 -2.09351011e-01]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[-1.11022302e-16 4.94396191e-17 -5.55111512e-17 -5.55111512e-17\n",
" 1.00000000e+00 -6.82301638e-01 -2.38434963e-02 -9.22987879e-03\n",
" -6.18611520e-01 3.88755140e-01]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 1.36462871e-01 7.01439691e-01 -3.17944976e-03 1.54319830e-01\n",
" -6.82301638e-01 1.00000000e+00 0.00000000e+00 -8.32667268e-17\n",
" -5.55111512e-17 4.16333634e-16]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 2.70633972e-01 -9.31695264e-02 -9.56044369e-01 5.90537418e-02\n",
" -2.38434963e-02 0.00000000e+00 1.00000000e+00 0.00000000e+00\n",
" -5.27355937e-16 4.71844785e-16]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 2.77863850e-01 -2.62497461e-01 1.60673947e-01 9.09937062e-01\n",
" -9.22987879e-03 -8.32667268e-17 0.00000000e+00 1.00000000e+00\n",
" 0.00000000e+00 -1.11022302e-16]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[ 3.60938307e-01 -6.01364392e-01 1.56586878e-01 -3.17623588e-01\n",
" -6.18611520e-01 -5.55111512e-17 -5.27355937e-16 0.00000000e+00\n",
" 1.00000000e+00 -2.77555756e-17]\n",
"Norm:\n",
"1.0000000000000002\n",
"Dots:\n",
"[ 8.37048599e-01 2.62216991e-01 1.88768343e-01 -2.09351011e-01\n",
" 3.88755140e-01 4.16333634e-16 4.71844785e-16 -1.11022302e-16\n",
" -2.77555756e-17 1.00000000e+00]\n"
]
}
],
"source": [
"for q in orthonormal_basis:\n",
" print(\"Norm:\")\n",
" print(np.linalg.norm(q))\n",
" print(\"Dots:\")\n",
" print(np.dot(orthonormal_basis, q))"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"#gram-shmidt-with-col-pivoting\n",
"\n",
"q_i_1 = np.argmax([np.linalg.norm(b) for b in basis])\n",
"\n",
"orthonormal_basis = [normalize(basis[q_i_1])]\n",
"done = [q_i_1]\n",
"\n",
"def get_basis(b, orthonormal_basis):\n",
" for o_b in orthonormal_basis:\n",
" b = b - np.dot(b, o_b)*o_b\n",
" return b\n",
"\n",
"for i in range(len(basis)-1):\n",
"# if i in done:\n",
"# continue\n",
" \n",
" best_j = None\n",
" best_basis = None\n",
" max_norm = -100000\n",
" for j in range(len(basis)):\n",
" if j in done:\n",
" continue\n",
" cur_basis = get_basis(basis[j], orthonormal_basis)\n",
" cur_norm = np.linalg.norm(cur_basis)\n",
" if cur_norm > max_norm:\n",
" max_norm = cur_norm\n",
" best_j = j\n",
" best_basis = normalize(cur_basis)\n",
" \n",
" done.append(best_j)\n",
" orthonormal_basis.append(best_basis)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[array([-0.16858878, 0.23804494, 0.89096286, -0.34625708, -0.03469365]),\n",
" array([-0.21262894, -0.91831748, 0.22770684, 0.03388898, 0.24183273]),\n",
" array([ 0.66975414, -0.30361036, 0.01987955, -0.43133643, -0.52230626]),\n",
" array([ 0.2699725 , -0.0230346 , 0.36842968, 0.83215694, -0.31362183]),\n",
" array([0.63632618, 0.08554393, 0.13490426, 0.02052499, 0.75442084]),\n",
" array([ 0.27846592, -0.27846592, -0.81219226, 0.42930162, -0.03094066]),\n",
" array([ 0.38474446, 0.3215286 , -0.37105555, -0.72130493, 0.30104491]),\n",
" array([-0.61656883, -0.60189122, -0.21423895, -0.37676618, 0.26404309]),\n",
" array([ 0.6214986 , -0.64018369, 0.39049289, -0.06393831, 0.2175581 ]),\n",
" array([ 0.08950309, -0.21672077, -0.06541021, -0.38649508, -0.88958662])]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"orthonormal_basis"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 1.00000000e+00 -2.30718222e-16 6.24500451e-17 2.94902991e-17\n",
" -2.08166817e-17 -9.84442048e-01 -7.96094568e-02 -1.08912174e-01\n",
" 1.05335692e-01 3.97330996e-02]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[-2.30718222e-16 1.00000000e+00 2.77555756e-17 2.77555756e-17\n",
" -2.77555756e-17 1.86346071e-02 -4.13206808e-01 6.86129969e-01\n",
" 5.95107056e-01 -6.31359113e-02]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 6.24500451e-17 2.77555756e-17 1.00000000e+00 0.00000000e+00\n",
" 5.55111512e-17 8.58898889e-02 3.06575815e-01 -2.09866468e-01\n",
" 5.32327448e-01 7.55789488e-01]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[ 2.94902991e-17 2.77555756e-17 0.00000000e+00 1.00000000e+00\n",
" -5.55111512e-17 1.49306751e-01 -7.34896896e-01 -6.27862562e-01\n",
" 2.04965397e-01 -3.75743919e-02]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[-2.08166817e-17 -2.77555756e-17 5.55111512e-17 -5.55111512e-17\n",
" 1.00000000e+00 2.92750197e-02 4.34580591e-01 -2.81262284e-01\n",
" 5.56209186e-01 -6.49465589e-01]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[-9.84442048e-01 1.86346071e-02 8.58898889e-02 1.49306751e-01\n",
" 2.92750197e-02 1.00000000e+00 2.72351586e-16 -1.71737624e-16\n",
" 2.25514052e-16 -1.65839564e-15]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[-7.96094568e-02 -4.13206808e-01 3.06575815e-01 -7.34896896e-01\n",
" 4.34580591e-01 2.72351586e-16 1.00000000e+00 6.93889390e-17\n",
" -8.32667268e-17 -2.77555756e-16]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[-1.08912174e-01 6.86129969e-01 -2.09866468e-01 -6.27862562e-01\n",
" -2.81262284e-01 -1.71737624e-16 6.93889390e-17 1.00000000e+00\n",
" 2.77555756e-17 2.77555756e-16]\n",
"Norm:\n",
"1.0\n",
"Dots:\n",
"[ 1.05335692e-01 5.95107056e-01 5.32327448e-01 2.04965397e-01\n",
" 5.56209186e-01 2.25514052e-16 -8.32667268e-17 2.77555756e-17\n",
" 1.00000000e+00 1.11022302e-16]\n",
"Norm:\n",
"0.9999999999999999\n",
"Dots:\n",
"[ 3.97330996e-02 -6.31359113e-02 7.55789488e-01 -3.75743919e-02\n",
" -6.49465589e-01 -1.65839564e-15 -2.77555756e-16 2.77555756e-16\n",
" 1.11022302e-16 1.00000000e+00]\n"
]
}
],
"source": [
"for q in orthonormal_basis:\n",
" print(\"Norm:\")\n",
" print(np.linalg.norm(q))\n",
" print(\"Dots:\")\n",
" print(np.dot(orthonormal_basis, q))"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[-0.00199824, -0.38741958, -0.47204596, 0.03228405, 0.20601819],\n",
" [ 0.1994896 , -0.26395664, -0.50479832, -0.28017554, 0.29929613],\n",
" [-0.4841608 , 0.39197138, -0.16150924, -0.33966832, -0.05895325],\n",
" [-0.26552477, -0.15008915, 0.41870949, -0.4742575 , 0.18788235],\n",
" [-0.0888581 , -0.24827178, -0.21760775, -0.24854418, -0.67851866],\n",
" [ 0.25343617, 0.18362567, 0.17339259, -0.215912 , -0.22477143],\n",
" [-0.60075385, 0.11650459, -0.32735933, -0.00914752, -0.03500784],\n",
" [ 0.27983293, 0.55002089, -0.35213975, 0.1613557 , -0.23405772],\n",
" [-0.10793611, -0.4388431 , 0.09970876, 0.24142419, -0.49330075],\n",
" [-0.36372697, -0.00527455, 0.0492128 , 0.62238853, 0.13761942]])"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Q, _ = np.linalg.qr(basis) #inbuilt\n",
"Q"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Norm:\n",
"0.6452992042954802\n",
"Dots:\n",
"[-0.53078791 0.29962697 -0.01462767 -0.20327756 0.05799311 0.49820404\n",
" 0.08855407 0.37778126 0.10520394 -0.08108901]\n",
"Norm:\n",
"0.7296348819301435\n",
"Dots:\n",
"[-0.45959271 0.14791744 0.16823947 -0.45306166 0.25630576 0.40950704\n",
" 0.4713847 0.32860932 0.17887133 -0.04988458]\n",
"Norm:\n",
"0.7300606344663485\n",
"Dots:\n",
"[ 0.15069001 -0.31955217 -0.26918303 -0.46341213 -0.34778896 -0.2567925\n",
" 0.22693758 0.20960523 -0.60601509 0.06600628]\n",
"Norm:\n",
"0.7270266490495072\n",
"Dots:\n",
"[ 0.53978783 0.31899475 -0.01751152 -0.36754282 0.00669435 -0.58163021\n",
" 0.09286368 0.39264098 0.16576299 -0.00246516]\n",
"Norm:\n",
"0.7994057475300068\n",
"Dots:\n",
"[-0.12839932 0.02482442 0.47313957 -0.09247306 -0.62412707 0.135424\n",
" -0.05825802 0.16532467 -0.11298565 0.75974857]\n",
"Norm:\n",
"0.47450338323935365\n",
"Dots:\n",
"[ 0.23803023 -0.24470598 0.32796647 0.01889459 0.02636369 -0.20712507\n",
" 0.18028288 -0.28193197 0.07256884 0.25494876]\n",
"Norm:\n",
"0.6949473829094591\n",
"Dots:\n",
"[-0.15826937 -0.06256855 -0.42200666 -0.2821125 -0.44306971 0.0633028\n",
" -0.07614944 0.36461903 -0.58281487 -0.02292767]\n",
"Norm:\n",
"0.7652780694362091\n",
"Dots:\n",
"[-0.27774068 -0.69591364 0.06607806 0.14081783 0.00434461 0.2872792\n",
" 0.22832647 -0.55074165 -0.37694466 0.07472993]\n",
"Norm:\n",
"0.718196759883151\n",
"Dots:\n",
"[-0.0639112 0.33753736 0.21644785 0.37331717 -0.45997294 0.13007049\n",
" -0.54227206 0.08811123 0.13003579 0.42444832]\n",
"Norm:\n",
"0.7355634664744216\n",
"Dots:\n",
"[-0.11636948 0.14776168 -0.58136624 0.39482115 -0.1086637 0.12314734\n",
" -0.56740083 0.01873663 -0.21331612 -0.39760511]\n"
]
}
],
"source": [
"for q in Q:\n",
" print(\"Norm:\")\n",
" print(np.linalg.norm(q))\n",
" print(\"Dots:\")\n",
" print(np.dot(orthonormal_basis, q))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment