Is it possible to solve for a directly without using the inverse?

[feenaboccles]

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

 

[whs]

Why don't you write your own Matlab function?

 

[feenaboccles]

Why don't you write your own Matlab function?

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.

 

[whs]

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.

 

[trambolin]

why don't you just take the transpose, then everything goes back to normal ?

 

[feenaboccles]

why don't you just take the transpose, then everything goes back to normal ?

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 x_m
X is m x d the datapoints x_m 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||² 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