0
$\begingroup$

I want to maximize the smallest nonzero singular value of (non-square) matrix $X$. This is equivalent to maximizing $\lambda_{\min}(X^\top X)$, which can be reformulated as follows

$$\begin{array}{ll} \underset{t, X}{\text{maximize}} & t\\ \text{subject to} & t \, \mathbb{I} - X^\top X \preceq 0\end{array}$$

One can reformulate the last constraint using the Schur complement iff $\mathbb{I}$ is negative semidefinite, which is absurd. So the claim is that the last constraint is non-convex. Is there any other tool to reformulate the last constraint as a convex constraint?

$\endgroup$
  • $\begingroup$ Perhaps maximize the trace $\endgroup$ – воитель May 16 at 18:53
  • 1
    $\begingroup$ I'm a little confused. Are there more constraints? Maximizing the smallest eigenvalue of $X^TX$ over all $X$ is clearly unbounded. Is $X$ given? In that case the constraint is clearly just linear in $t$... $\endgroup$ – Travis C Cuvelier May 16 at 19:18
  • $\begingroup$ You can add a Frobenius norm constant on X and constain it by some known constant C $\endgroup$ – Rohit Arora May 16 at 19:47
  • $\begingroup$ Is $X$ fat or tall? $\endgroup$ – Rodrigo de Azevedo May 20 at 5:51
  • $\begingroup$ $X$ is a fat matrix $\endgroup$ – Rohit Arora May 20 at 22:07
1
$\begingroup$

I'm not totally sure if this is answering your question, but let $\boldsymbol{\lambda}$ be a vector that you can think of as containing the eigenvalues of $\mathbf{X}^T\mathbf{X}$. I'm assuming that the Frobenius norm constraint you mentioned in your comment is of the form $||X||_{F}^2 \le c$. Let $\mathbf{1}$ be a vector of all 1s. Assume $\mathbf{X} \in \mathbb{R}^{M\times N}$. I think you should start with the program:

$$\max_{\lambda,t} t$$ $$\text{st. } \mathbf{1}t \preccurlyeq \boldsymbol{\lambda}$$ $$\boldsymbol{\lambda} \succcurlyeq 0$$ $$\mathbf{1}^T\boldsymbol{\lambda} \le c$$

If, by chance, you wanted a constraint of the form $||X||_{F}^2 = c$ you should start with:

$$\max_{\lambda,t} t$$ $$\text{st. } \mathbf{1}t \preccurlyeq \boldsymbol{\lambda}$$ $$\boldsymbol{\lambda} \succcurlyeq 0$$ $$\mathbf{1}^T\boldsymbol{\lambda} = c$$

Both of these are clearly linear programs. You can find an $\mathbf{X}$ that achieves the solution easily enough. First put $\boldsymbol{\lambda}$ into a diagonal matrix, say $\mathbf{S}$ and augment it with the appropriate number of zeros such that it has the same dimensions of $\mathbf{X}$, ie $$ \begin{bmatrix}\lambda_1 &0 &0 \\ 0& \ddots &0 \\ 0& 0 & \lambda_N \\ 0 & 0 & 0\\ \vdots & \vdots & \vdots \end{bmatrix}.$$ Pick your favorite orthogonal matrix $\mathbf{V}\in\mathbb{R}^{M\times M}$ and your second favorite orthogonal matrix $\mathbf{U}\in\mathbb{R}^{N\times N}$. Let $\mathbf{R} = \sqrt{\mathbf{S}}$ (elementwise I guess, idk if the matrix square root is technically allowed for non-square matrices). Let $\mathbf{X} = \mathbf{V}\mathbf{R}\mathbf{U}^T$ then clearly $$\mathbf{X}^T\mathbf{X} = \mathbf{U}\mathbf{S}\mathbf{U}^T.$$ This matrix has the eigenvalues that you want.

$\endgroup$
  • $\begingroup$ Thank you for the solution. The solution is not unique. It depends on the choice of $U$ and $V$ $\endgroup$ – Rohit Arora May 16 at 22:43
  • $\begingroup$ That's sort of right. There's only one maximum, but there's infinitely many maximizers. $\endgroup$ – Travis C Cuvelier May 16 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.