Prev: Proof that function is positive
Next: probably a bird like geese is third Re: AP's theory that the dog was the first domesticated animal theory
From: approxnn on 20 Jul 2010 08:01
I have the following optimization problem that I want to solve.

- W is a KxN binary valued matrix
- maximize trace(W'W) w.r.t. W
- condition: each row and each column of W can have only a single 1

Please suggest any approach to solve this.

Thanks.
From: Chip Eastham on 20 Jul 2010 10:21
On Jul 20, 8:01 am, "appro...(a)gmail.com" <appro...(a)gmail.com> wrote:
> I have the following optimization problem that I want to solve.
>
> - W is a KxN binary valued matrix
> - maximize trace(W'W) w.r.t. W
> - condition: each row and each column of W can have only a single 1
>
> Please suggest any approach to solve this.
>
> Thanks.

If K and N are allowed to be unequal, presumably
you mean that each row and column of W can have
a most a single 1 (and the rest zeros).

Since trace(W'W) = trace(WW'), we can assume wlog
that K =< N. Since trace(WW') is the sum of all
norms squared of rows in W, it is clear that if
K = N, the maximum trace(W'W) = K is attained
whenever all rows are nonzero.

If K < N, then a matrix [I|0] attain a trace
of K. It seems to me that basically the same
argument applies as above, and this is indeed
the maximum (attained whenever all rows of W
have a single 1, in distinct columns of course).

regards, chip
 | 
Pages: 1
Prev: Proof that function is positive
Next: probably a bird like geese is third Re: AP's theory that the dog was the first domesticated animal theory