Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help solving an eqn in Matlab

  1. Oct 19, 2009 #1
    I'm working on a project where the following has to be solved on a regular basis, as new column vectors are added to the matrix X.

    a = x' * inv (X * X') * X

    where
    m is the number of examples
    d is the dimensionality of the vector x
    x is d x 1 and norm2(x) <= 1
    X is d x m, consisting of m "x" vectors arranged column-wise (not row-wise as is typically the case)
    and
    a should be m x 1

    I'm wondering is there a faster way to calculate in Matlab, other than a direct implementation of the above. It's not an equation in the usual form Xw = y, so the built-in solver won't work. I'm wondering are there any decompositions that might help, but bear in mind that the equation is solved, then X is changed, then we return to solve the equation once more for a different x.

    Thanks
     
  2. jcsd
  3. Oct 19, 2009 #2

    whs

    User Avatar

    Why don't you write your own Matlab function?
     
  4. Oct 19, 2009 #3
    The code in my original post is Matlab code which does solve the equation. My question is not particularly Matlab-centric: it's whether the problem can be re-phrased, through some factorisation or decomposition, which would expedite its solution. Particularly, I'm wondering can it be rephrased in such as way that I can employ the heavily optimised solvers one finds in Matlab and various lin alg libraries like BLAS.
     
  5. Oct 19, 2009 #4

    whs

    User Avatar

    Ah, I don't know the answer, but you might want to try posting this (or getting it moved) to the computers/math software section where there are lots of matlab/mathematica type questions.
     
  6. Oct 19, 2009 #5
    why don't you just take the transpose, then everything goes back to normal ?
     
  7. Oct 20, 2009 #6
    Actually it won't.

    Take a standard linear regression problem
    X * w = y
    where
    m is the number of training samples
    d is the dimensionality of each training sample xm
    X is m x d the datapoints xm arranged row-wise
    y is m x 1
    w is d x 1

    The standard equations are (less regularization) are
    w = inv(X' * X) * X' * y

    Or

    w' = y' * X * inv (X' * X)'

    If you say Z = X' (i.e datapoints are arranged column wise, rather than row-wise), you get

    w' = y * Z' * inv (Z * Z')'


    Now consider my example. In my example I'm expression a new datapoint as a linear combination (the vector a) of all previous datapoints. This is different to the standard regression problem. Hence, whereas w above is d x 1, a is m x 1. So, if we have a new datapoint z, and we want to express it as a linear combination of previous datapoints arranged column-wise in Z. We minimise ||a||2 subject to z = Z * a and thereby get

    a = z' * inv (Z * Z') * Z

    My question is is there any way of rephrasing this so the inverse can be avoided, and the problem solved directly.

    The key diffence in the equations for a and w' is the first term, y is m x 1, but z is d x 1
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help solving an eqn in Matlab
Loading...