Skip to content

Instantly share code, notes, and snippets.

@iizukak
Created October 14, 2011 18:18
Show Gist options
  • Save iizukak/1287876 to your computer and use it in GitHub Desktop.
Save iizukak/1287876 to your computer and use it in GitHub Desktop.
Gram-Schmidt Orthogonization using Numpy
import numpy as np
def gs_cofficient(v1, v2):
return np.dot(v2, v1) / np.dot(v1, v1)
def multiply(cofficient, v):
return map((lambda x : x * cofficient), v)
def proj(v1, v2):
return multiply(gs_cofficient(v1, v2) , v1)
def gs(X):
Y = []
for i in range(len(X)):
temp_vec = X[i]
for inY in Y :
proj_vec = proj(inY, X[i])
temp_vec = map(lambda x, y : x - y, temp_vec, proj_vec)
Y.append(temp_vec)
return Y
#Test data
test = np.array([[3.0, 1.0], [2.0, 2.0]])
test2 = np.array([[1.0, 1.0, 0.0], [1.0, 3.0, 1.0], [2.0, -1.0, 1.0]])
print np.array(gs(test))
print np.array(gs(test2))
@seralouk
Copy link

There is indeed a problem with the code. n should be number of columns and not rows: n = A.shape[1].

Exactly. I just wanted to check that I am not missing something here. n = A.shape[1] should be fine

@AmerHussein
Copy link

AmerHussein commented Sep 13, 2019

Maybe using list comprehension would make the code a bit less sluggsih for bigger matrices...so this version uses taht, You can even use it to check if a suspected "orthogonal" matric is actually othogonal by automatic_check=True. To check if you had two or more linearly dependent vectors used in the process, simply set orthogonality_check=True, and if the fucntion return False, then you had a linearly dependent vector in your set of vectors.

def Grahm_Schmidt(matrix, orthogonality_check=False, automatic_check=False, error_tol=1.e-10):
     """
     matrix is a matrix whose rows are  vectors to be turned into an ON-basis
     """
     veclist = list(matrix)
     newbasis = []
     def orth_check(Matrix):
          """
          This fucntion check for the pairwise orthogonality of the new basis
          """
          list_ = list(Matrix)
          dot_matrix = np.array([[m(item1, item2) for item1 in list_] for item2 in list_])
          if (dot_matrix - np.eye(dot_matrix.shape[0]) < error_tol).all():
               return True
          else:
               error = dot_matrix - np.eye(dot_matrix.shape[0])
               return False, np.max(error), np.min(error)

     def m(a,b):
               return np.matmul(a,b)
     def n(a):
          return np.linalg.norm(a)

     def motor(vector, ind):
          if ind == 0:
               new = vector/n(vector)
          else:
               L = np.array([newbasis[i]*m(newbasis[i],vector) for i in range(len(newbasis))])
               projections = np.sum(L, axis=0)
               NEW = vector - projections
               new = NEW/n(NEW)
          newbasis.append(new)
          
     [motor(vector, ind) for ind,vector in enumerate(veclist)]
     newbasis_matrix = np.array(newbasis)

     if orthogonality_check and automatic_check == False:
          return orth_check(newbasis_matrix)

     elif automatic_check:
          return orth_check(matrix)

     else:
          return newbasis_matrix

@louity
Copy link

louity commented Sep 22, 2019

Pytorch version :

import torch    
def orthonormalize(vectors):    
    """    
        Orthonormalizes the vectors using gram schmidt procedure.    
    
        Parameters:    
            vectors: torch tensor, size (dimension, n_vectors)    
                    they must be linearly independant    
        Returns:    
            orthonormalized_vectors: torch tensor, size (dimension, n_vectors)    
    """    
    assert (vectors.size(1) <= vectors.size(0)), 'number of vectors must be smaller or equal to the dimension'    
    orthonormalized_vectors = torch.zeros_like(vectors)    
    orthonormalized_vectors[:, 0] = vectors[:, 0] / torch.norm(vectors[:, 0], p=2)    
    
    for i in range(1, orthonormalized_vectors.size(1)):    
        vector = vectors[:, i]    
        V = orthonormalized_vectors[:, :i]    
        PV_vector= torch.mv(V, torch.mv(V.t(), vector))    
        orthonormalized_vectors[:, i] = (vector - PV_vector) / torch.norm(vector - PV_vector, p=2)    
    
    return orthonormalized_vectors

@aditya0by0
Copy link

Similar to @ingmarschuster 's vectorized version

def gram_schmidt(A,norm=True,row_vect=False):
    """Orthonormalizes vectors by gram-schmidt process
    
    Parameters
    -----------
    A : ndarray,
    Matrix having vectors in its columns
    
    norm : bool,
    Do you need Normalized vectors?
    
    row_vect: bool,
    Does Matrix A has vectors in its rows?
    
    Returns 
    -------
    G : ndarray,
    Matrix of orthogonal vectors 
    
    """
    if row_vect :
        # if true, transpose it to make column vector matrix
        A = A.T
    
    no_of_vectors = A.shape[1]
    G = A[:,0:1].copy() # copy the first vector in matrix
    # 0:1 is done to to be consistent with dimensions - [[1,2,3]]
    
    # iterate from 2nd vector to number of vectors
    for i in range(1,no_of_vectors):
        
        # calculates weights(coefficents) for every vector in G
        numerator = A[:,i].dot(G)
        denominator = np.diag(np.dot(G.T,G)) #to get elements in diagonal
        weights = np.squeeze(numerator/denominator)
        
        # projected vector onto subspace G 
        projected_vector = np.sum(weights * G,
                                  axis=1,
                                  keepdims=True)
        
        # orthogonal vector to subspace G
        orthogonalized_vector = A[:,i:i+1] - projected_vector
        
        # now add the orthogonal vector to our set 
        G = np.hstack((G,orthogonalized_vector))
        
    if norm :
        # to get orthoNORMAL vectors (unit orthogonal vectors)
        # replace zero to 1 to deal with division by 0 if matrix has 0 vector
        G = G/replace_zero(np.linalg.norm(G,axis=0))
    
    if row_vect:
        return G.T
    
    return G
def replace_zero(array): 
    
    for i in range(len(array)) :
        if array[i] == 0 : 
            array[i] = 1
    return array
G = np.array([[1,0,0],[1,1,0],[1,1,1],[1,1,1]])
gram_schmidt(G)
>
array([[ 0.5       , -0.8660254 ,  0.        ],
       [ 0.5       ,  0.28867513, -0.81649658],
       [ 0.5       ,  0.28867513,  0.40824829],
       [ 0.5       ,  0.28867513,  0.40824829]])
B = np.array([[1,0],[-2,0],[2,0]])
gram_schmidt(B)
>
array([[ 0.33333333,  0.        ],
       [-0.66666667,  0.        ],
       [ 0.66666667,  0.        ]])

@pranoy-ray
Copy link

Is there a 3D implementation of this procedure? I have n image in a non-orthogonal 3D system and I am trying to convert it to an orthogonal 3D image.

@PierrickPochelu
Copy link

PierrickPochelu commented Nov 16, 2022

I simply implemented formula from a book (Maths for ML) and it is working fine with any matrix dimension (eg., 4x5).

import numpy as np
from numpy.linalg import inv

def _from_basis_to_project_matrix(B):
    """Formula page 87 book 'Maths For ML' """
    inv_Bt_B = inv(np.dot(B.T, B))
    proj_matrix = np.dot(B, np.dot(inv_Bt_B, B.T))
    return proj_matrix

def _projec(x, basis):
    """project `x` in the new vector space defined by `basis` """
    proj_matrix = _from_basis_to_project_matrix(basis)
    proj_x = np.dot(proj_matrix, x)
    return proj_x

def _get_col(x, col_id):
    """return column `col_id` from matrix `x` """
    raw_col_val = x[:, col_id]
    col_as_row = np.array([raw_col_val]).T
    return col_as_row

def gram_schmidt(B):
    nb_col = B.shape[1]
    first_col=_get_col(B, 0)
    
    U_vecs = [first_col]
    
    for i in range(1, nb_col):
        B_i = _get_col(B, i)
        U_i_1 = np.concatenate(U_vecs, axis=1)
        p = _projec(B_i, U_i_1)
        U_i = B_i - p
        U_vecs.append(U_i)

    return U_vecs

if __name__ == '__main__':
    # B=np.array([[2,1],[0,1]])
    # B=np.array([[1,0],[1,1],[1,2]])
    B = np.array([[0, 1, -3, -1],
                  [-1, -3, 4, -3],
                  [2, 1, 1, 5],
                  [0, -1, 2, 0],
                  [2, 2, 1, 7]
                  ])

    U = gram_schmidt(B)

    print(np.round(U, 2))

@egoughnour
Copy link

Is there a 3D implementation of this procedure? I have n image in a non-orthogonal 3D system and I am trying to convert it to an orthogonal 3D image.

If you are working solely with vectors, then there is no problem with any number of dimensions (assuming you have sufficiently many linearly independent vectors to form an orthonormal basis).

This should be fine even if you are using an MxNxP (matrix/tensor, whatever). In that case you'd be able to use vectors of length MP or NP. Just have some mapping from the interval [1,MP] to a "2D" slice of the "3D" object.
For instance, take phi: x -> (x // M, x % M) [or something like it] to map x, the index into the vector, to i.j the indices in the slice.
phi would then just fill rows or columns (depending on whether you're using a row-major convention or not).

#  this maps a vector of length 25 to a 5x5 matrix
for x in range(1,25):
    print(f'({x // 5},{x % 5})')

Linearity shouldn't be compromised by the method you use to traverse the "lower-dimensional" slice.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment