|
|
Re: sum of matrices
Posted:
Oct 8, 2012 1:29 PM
|
|
On 08/10/2012 1:26 PM, Rupert wrote:
> On Oct 8, 6:17 pm, Kiuhnm <kiuhnm03.4t.yahoo.it> wrote:
>> On 10/8/2012 16:45, Rupert wrote:
>>
>>> On Oct 8, 4:18 pm, Kiuhnm <kiuhnm03.4t.yahoo.it> wrote:
>>>> On 10/8/2012 13:35, Kiuhnm wrote:
>>
>>>>> Let X_1,...,X_m and Y_1,...,Y_m be column vectors of length n.
>>>>> I need to compute
>>>>> Sum_{i=1}^m X_i^T Y_i
>>>>> The trivial algorithm takes time O(m n^2). Can we do better?
>>
>>>> Sorry. I meant
>>>> Sum_{i=1}^m X_i Y_i^T
>>
>>>> Kiuhnm
>>
>>> Well, you need to look at mn^2 pieces of data, it would seem, so it's
>>> hard to see how you could get around that.
>>
>> I think I've found a way.
>> Let assume that m = n.
>> The i,j element of the final matrix is given by
>> Sum_{k=1}^n {X_k}_i {Y_k}_j
>> But that looks like a sort of dot product, doesn't it?
>> So, if X and Y are nxn matrices where X_{i,j} = {X_j}_i and Y_{i,j} =
>> {Y_i}_j, then the sum above becomes
>> Sum_{k=1}^n X_{i,k} Y_{k,j}
>> that is
>> [XY]_{i,j}
>> So we can solve the problem in O(n^{2+o(1)})
>> Does it make sense?
What in the world do you mean by O(n^{2+o(1)})? Isn't that just O(n^3)
as before? If not, explain a bit better how you want to take n^2 dot
products with, on average, less than n operations each.
|
|
