8
$\begingroup$

Let $A$ be a given symmetric positive definite $N\times N$ matrix. I need to find a symmetric positive semi-definite matrix $S$ which is the solution to the following optimization problem \begin{align} \max_{S}~&\det(A+S) \\s.t.~&\sum_{i}^{N}\sigma_i(S)\,=\,c \\&S\geq0 \end{align}where $\sigma_i(S)$ are the singular values of $S$ and $c$ is a given positive constant.

Note that I already know that this can be converted into a standard convex problem by replacing the constraint on sum of singular values by trace and also considering log-determinant. However, I am interested in a different approach.

My hunch is that following is the solution.

Let $A=U_a\Sigma_aU_a^H$ be its Eigen-decomposition (EVD). Since both $A$ and $S$ are symmetric positive semi-definite, their EVD and SVD are same. Let $S= U_s\Sigma_sU_s^H$ be its EVD which we are seeking. Then first part of the solution is $$U_s = U_a$$ It only remains find $\Sigma_s$ which contains the singular values of $S$. Substituting this in the original optimization problem, it breaks down into the simple form of finding the variables $\sigma_i(S)$ from the optimization problem \begin{align} \max_{\sigma_1(S),\dots,\sigma_N(S)}~&\prod_{i=1}^{N}(\sigma_i(A)+\sigma_i(S)) \\s.t.&\sum_{i=1}^N\sigma_i(S)=c \end{align} This is also equivalent to maximizing the $\log$ of the objective since the objective is a increasing function of each variable. Let us substitute $$x_i=\frac{\sigma_i(S)}{\sigma_i(A)}$$ Also, we can use the fact that determinant is the product of singular values for a symmetric positive definite matrix. Combining all this, we have the optimization problem \begin{align}\max_{x_i}\sum_{i=1}^{N}~&\log(1+x_i)+\log\det(A)\\s.t.~&\sum_{i=1}^{N}\sigma_i(A)x_i\,=\,c\end{align} The constant term in the objective can be neglected. This is an instance of a very famous problem in wireless communications where one tries to maximize the capacity of set of $N$ wireless channels subject to power constraints in each. Its solution is very well known and is typically referred to as the water filling solution. So I know the process after reaching this point. Note that all this was facilitated by the assumption that $U_s = U_a$. Is that true? How do I prove this?. If not, what are other approaches I can try?

$\endgroup$
  • $\begingroup$ Just curious: can you mention some link to some wireless communication paper or give some name for this particular optimisation problem? $\endgroup$ – Sergey Dovgal Oct 25 '17 at 3:21
  • $\begingroup$ @SergeyDovgal sorry for a late reply. Please google for waterfilling in context of wireless communications. You will easily come across this. $\endgroup$ – dineshdileep Dec 13 '17 at 10:04
5
$\begingroup$

One can verify that $U_{A}=U_{S}$ as follows. Note that $$\det(U_{A}\Sigma_{A}V_{A}^{T}+U_{S}\Sigma_{S}V_{S}^{T})=\det(\Sigma_{A}+U_{A}^{-1}U_{S}\Sigma_{S}V_{S}^{T}V_{A}^{-T})$$ Let $Y=U_{A}^{-1}U_{S}\Sigma_{S}V_{S}^{T}V_{A}^{-T}$ so that the problem can be rephrased as:

$$\max\limits_{Y} \det(\Sigma_{A}+Y) \text{ subject to } Tr(Y)=c,\ Y\succ 0$$

Now, let $Z=\Sigma_{A}+Y$ so that the problem is reformulated:

$$\max\limits_{Z} \det(Z) \text{ subject to } Tr(Z)=c+\sum\limits_{i=1}^{n} \sigma_{A}(i),\ Z\succ 0,\ Z_{i,i}\geq \sigma_{A}(i)$$

Since $Z$ can be written $Z=UT$ where $U$ is orthogonal and $T$ upper triangular, $\det(Z)=\det(T)$ and the off-diagonal terms of $T$ do not contribute so that $T$ may be assumed diagonal. Thus, finally one arrives at:

$$\max\limits_{T} \det(T) \text{ subject to } Tr(T)=c+\sum\limits_{i=1}^{n} \sigma_{A}(i),\ T\succ 0,\ T_{i,i}\geq \sigma_{A}(i),\ \text{T is diagonal}$$

This problem's solution follows from solving the water filling problem above where $t_{k}=T_{k,k}$:

$$\max\limits_{t_{k}} \sum\limits_{k=1}^{n} \log(t_{k}+\sigma_{k}) \text{ subject to } t_{k}\geq 0 \text{ and }\sum\limits_{k=1}^{n} t_{k}=c$$

$\endgroup$
1
$\begingroup$

Your constraints are linear on the entries of $S,$ since in your case the singular values are equal to the eigenvalues (since $S$ is symmetric positive definite) and so their sum is the trace. I assume the last inequality $S\geq 0$ is elementwise. Log determinant is a convex function, and so your problem is a box-standard semi-definite programming problem, which you can read about in Boyd-Vanderberghe (available for free on Stephen Boyd's web site at Stanford).

$\endgroup$
  • 1
    $\begingroup$ $S\geq 0$ is not element-wise, it implies that the matrix is positive semi-definite. Still, it is a convex problem once I consider Log-Determinant and I can use out-of-box SDP methods to solve this. However, I need to know whether $A$ and $S$ will have the same set of Eigen vectors. Going that route will also bring huge computational savings as well. $\endgroup$ – dineshdileep Dec 13 '17 at 4:43
  • 1
    $\begingroup$ @dineshdileep Since you already state that $S$ is positive definite, I assumed that this was an extra condition. $\endgroup$ – Igor Rivin Dec 13 '17 at 5:43
0
$\begingroup$

See the discussion of Schur-convex/concave of the determinant function in

D. P. Palomar, J. M. Cioffi and M. A. Lagunas, "Joint Tx-Rx beamforming design for multicarrier MIMO channels: a unified framework for convex optimization," in IEEE Transactions on Signal Processing, vol. 51, no. 9, pp. 2381-2401, Sept. 2003.

http://www.ece.ust.hk/~palomar/Publications_files/2003/TransSP2003_convexJTRbf.pdf

$\endgroup$

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.