Results 1 to 1 of 1

Math Help - Optimisation with PSD and rank constraints

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    21

    Optimisation with PSD and rank constraints

    I have the following optimisation problem:

    \begin{array}{ll}\min_M  &  E(M) = \sum_i f_i(\mathbf a_i^T M \mathbf a_i)\\ \text{s.t.} & M \succeq 0\\&\mathrm{rank}(M) \leq k\end{array}

    where M is a (NxN) matrix \mathbf a_i's are constant vectors and f_i's are convex fonctions.
    I think that this is a convex optimisation problem.

    To avoid having to deal with the constraint I factorize the matrix M=L^TL, where L is a (k\times N) matrix. This ensures that M is PSD and of rank k at most. But the problem is not convex any more.

    \min_L F(L) = \sum_i f_i(\mathbf a_i^T L^T L \mathbf a_i)

    However in practicle applications, gradient descent based methods seem to lead to good solutions, and I would have to proove it.

    My intuition is that the minima when optimizing over L, correspond to minima of the constrained problem and that other correspond either to maxima either to saddle points, which would mean that an iterative optimisation process based on gradient descent has very low probabilities to get stuck at a 0 gradient point which is not the minimum.

    the gradient wrt to L is:
    \frac{\partial F(L)}{\partial L} = 2L \sum_i  f'_i(\mathbf a_i^T L^T L \mathbf a_i) \mathbf a_i \mathbf a_i^T

    How can I proove that or at least get some hints weither it's true or not ?
    Last edited by AlexisM; October 20th 2011 at 05:23 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Row Rank = Column Rank?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 9th 2011, 12:10 AM
  2. Proof: rank(AB)+n >= rank(A)+rank(B)
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: September 9th 2010, 05:28 PM
  3. Replies: 3
    Last Post: August 20th 2010, 05:32 AM
  4. Row rank and column rank
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 13th 2010, 07:40 AM
  5. Short proof that rows-rank=column-rank?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: June 26th 2009, 10:02 AM

Search Tags


/mathhelpforum @mathhelpforum