0

$$\begin{array}{ll} \text{maximize} & \mbox{tr} (A^T B A)\\ \text{subject to} & A^T A = I\end{array}$$

where the maximization is over $A$.

I know that the solution is eigenvectors of $B$, but I don't know how to arrive at it. In particular, constructing the Lagrangian is not straightforward because the constraint is a matrix equation while the objective function is scalar.

Rodrigo de Azevedo
  • 20,693
  • 5
  • 43
  • 100
Alex
  • 121
  • 4
  • P.S: it is known that B is symmetric. – Alex Apr 10 '19 at 22:17
  • Are you assuming that $B$ is symmetric? – Brian Borchers Apr 10 '19 at 22:18
  • @BrianBorchers YES! very smart of you to realize that. It is given indeed that it is symmetric. – Alex Apr 10 '19 at 22:19
  • Just a note: if $A$ is square, this problem is quite simple. By the [cyclic property](https://en.wikipedia.org/wiki/Trace_(linear_algebra)#Cyclic_property) of the trace, we have that $\mathrm{Tr}(A^TBA)=\mathrm{Tr}(BAA^T)$. Moreover, $A^TA=I$ iff $AA^T=I$ (see, _e.g._, [here](https://math.stackexchange.com/q/3852/398989)). Hence, the objective value always equals $\mathrm{Tr}(B)$ no matter your choice of $A$. – David M. Apr 11 '19 at 01:14
  • 1
    So, is $A$ expected to be non-square? – Brian Borchers Apr 11 '19 at 02:43
  • @DavidM. Actually, the constraint wasn't part of the original problem. It was later added because it was thought that it is ill-defined that way and there're infintely many solutions. Many constraints can be added (only condition is that they should be sensible in some sense understood by domain specialists). So, this constraint that you find was added and it is thought of as a good constraint. As for the size of A, it can be square, but we generally want to do dimensionality reduction, and as such, the solution says: pick the m-leading eigen vectors. m is new dimension that we want. – Alex Apr 11 '19 at 04:27
  • Here is the original problem by a datascience professor https://www.youtube.com/watch?v=DkdrFwevais Watch @ 43:47 I simplified the problem for you here, but it is the same. – Alex Apr 11 '19 at 04:32
  • Let me take you to the bottom line, A is actually just a vector. Now give me the solution(s). (there are many of them, say I want 3). – Alex Apr 11 '19 at 08:28
  • I solved it with my last assumption. Piece of cake. Check my answer. – Alex Apr 11 '19 at 08:43

1 Answers1

0

Say instead of A, we solve for columns of A one by one.

max $u^TBu$

such that $u^Tu=1$

Construct the lagrangian, then differentiate to get:

$dL/du$=2Bu-2 $\lambda u$

Equate to zero, solve, you end up with Eigen decomposition problem of B.

Now pick the Eigen vector that corresponds to the largest Eigen value. If you want more solutions (more colums to A, pick the second and the third Eigen vectors that corresponds to second and third largest Eigen value and so on)

Alex
  • 121
  • 4