1
$\begingroup$

Suppose I have a matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$. Let $\{\sigma_1,\sigma_2,.....,\sigma_n \}$ be its $n$ singular values. Calculating a sub-gradient of its operator norm (largest singular value) is a well known result. Are more general results available i.e can we find the sub-gradient of the function ( of the matrix $A$) that produces as output the second largest singular value, third largest singular value and generally p-th largest singular value ($p=1,2,...,n$). Is it a well posed question at all.

$\endgroup$
2
  • $\begingroup$ What do you mean by subgradient of an eigenvalue? $\endgroup$ Sep 23, 2019 at 9:15
  • $\begingroup$ I meant , if we treat the $p-th$ largest singular value as a function of the matrix $\mathbf{A}$. Once we have a function of the matrix, then we can talk about subgradients of that function. I edited the question to reflect your question $\endgroup$ Sep 23, 2019 at 9:20

1 Answer 1

1
$\begingroup$

As an application of the Min-Max Theorem You get $$\sigma_{j+1}=\min_{x_1,..,x_j\in\mathbb{R}^n}\quad\max_{x\in\mathbb{R}^n||x||=1\\(x,x_1)=...=(x,x_j)=0}||Ax||.$$ As You see for $j=0$ you get $\sigma_1=|||A|||$ where $|||.|||$ is the operator norm. Of course the singular values are numbered in non-increasing order.Here $j=0,..,n-1$. The result can be generalized to ( possibly infinite-dimensional) Hilbert-spaces and compact operators.

$\endgroup$
5
  • $\begingroup$ Thank you @Peter Melech. If I understand correctly, the above formulation expresses each of the singular values as an optimization problem. But does this formulation help us in finding the sub-gradient of function $f_p(\mathbf{A})$ $\endgroup$ Sep 23, 2019 at 10:02
  • $\begingroup$ As far as I understand it sub-gradient methods are a kind of methods solving optimization problems and as far as I can see it, these optimization problems, that the Min-max Theorem yields, would be those that one should try to solve by sub-gradients.@Engineer_2018 $\endgroup$ Sep 23, 2019 at 10:12
  • $\begingroup$ Subgradient of a function is a generalization of the concept of gradient to nonsmooth functions. My question asks how we can calculate one of those subgradients ( as it is a set ). Thanks for the suggestion, I will check if the min max theorem can lead to any subgradients $\endgroup$ Sep 23, 2019 at 10:20
  • $\begingroup$ Good luck! At least $\{x\in\mathbb{R}^n :||x||=1,(x,x_1)=...=(x,x_j)=0\}$ is convex for $j=0,...,n-1$. $\endgroup$ Sep 23, 2019 at 10:25
  • $\begingroup$ Thanks a lot.@Peter Melech $\endgroup$ Oct 3, 2019 at 7:10

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.