3
$\begingroup$

After some searching I couldn't find an existing solution that lets you compute orthogonal (not orthonormal basis) without computing huge performance penalty relative to Orthogonalize. Any suggestions how to speed it up?

Two versions below compute desired quantity, but 30x slower than built-in Orthogonalize. It doesn't seem to be possible to use Orthogonalize with custom dot product function to achieve this (suggested in earlier version)

d = 200;
numSamples = d;
sigma = DiagonalMatrix[Table[1., {i, 1, d}]];
dist = MultinormalDistribution[sigma];
data = RandomVariate[dist, numSamples];
data = Normalize /@ data;

(* Version from https://mathematica.stackexchange.com/a/37357/217 *)
GramSchmidt[w_?MatrixQ] := Module[{v = ConstantArray[0, Length[w]]},
   Table[
    v[[n]] = 
     w[[n]] - 
      Sum[(v[[i]] . w[[n]]/v[[i]] . v[[i]])*v[[i]], {i, 1, 
        n - 1}], {n, 1, Length[w]}];
   v];


(* modified version from \
https://mathematica.stackexchange.com/a/101463/217 *)
proj[u_, v_] := v . u/u . u u;
gsOrthogonal[vectorSet_?MatrixQ] := 
  Map[With[{norm = Norm[#]}, If[norm > 0, #, #]] &, 
   Fold[Function[{spanVec, v}, 
       Join[spanVec, {v - 
          Total@Map[proj[#, v] &, 
            spanVec]}]][#1, #2] &, {vectorSet[[1]]}, 
    Drop[vectorSet, 1]]];


Print["Built-in timing: ", First@Timing@Orthogonalize[data]]
Print["version1 timing: ", First@Timing@GramSchmidt@data]
Print["version2 timing: ", First@Timing@gsOrthogonal@data]

Produces

Built-in timing: 0.021098

version1 timing: 0.829932

version2 timing: 0.629197
$\endgroup$
1
  • $\begingroup$ Version 13.1: Help for "Orthogonalize": Orthogonalize[{Subscript[e, 1],Subscript[e, 2],[Ellipsis]},f] gives an orthonormal basis found by orthogonalizing the elements Subscript[e, i] with respect to the inner product function f. $\endgroup$ Commented Jul 28, 2022 at 18:49

1 Answer 1

7
$\begingroup$

One can use a QR decomposition:

GramSchmidt[M_] := With[{qr=QRDecomposition[Transpose[M]]},
                     Diagonal[Last[qr]]*First[qr]];
$\endgroup$
1
  • $\begingroup$ Thanks, that turns out to be 5x faster than Orthogonalize $\endgroup$ Commented Jul 28, 2022 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.