0
$\begingroup$

I have the following function for two matrices ${\bf A}$ and ${\bf B}$:

$f({\bf A}, {\bf B}) = \| {\bf Y - XAB} \|_F^2 = trace\{({\bf Y - XAB)}^T({\bf Y - XAB)}\}$

where matrices ${\bf X}_{n \times p}$ and ${\bf Y}_{n \times q}$ are fixed, and matrices ${\bf A}_{p \times r}$ and ${\bf B}_{r \times q}$ are the variables, with $r<\min(p,q)$. I'd like to know whether this function is convex in both ${\bf A}$ and ${\bf B}$. (I am quite sure if either ${\bf A}$ or ${\bf B}$ is fixed, then, $f$ is convex for the other one.)

If it is not convex, can I impose some extra constraints on any of these matrices to make $f$ convex?

$\endgroup$

2 Answers 2

3
$\begingroup$

$f$ is convex separately for $A$ or $B$ but is not (in general) for the couple $(A,B)$.

Proof: The Hessian of $f$ in $X,Y$ is the following QUADRATIC form:

$Q(H,K)=2(||XHB+XAK||^2+2trace((XAB)^TXHK))-4trace(Y^TXHK)$.

Then $Q(H,0)=2||XHB||^2$ and $f$ is convex for $A$ (and similarly for $B$) - One must say a little more if there is $H\not=0$ s.t. $XHB=0$ -

The problem is clear when, as Robert wrote above, $Y=0$. Moreover, take $H=A,K=-B$ and assume that $XAB\not=0$. Then $Q(A,-B)=-4trace((XAB)^T(XAB))<0$. Thus $Q$ is not non-negative and $f$ is not convex.

EDIT (answer to Mkl). $H=0$ iff $XHB=(X\bigotimes B^T)(H)=0$ that is $X\bigotimes B^T$ is one to one, or $rank(X\bigotimes B^T)=pr$ (necessarily $pr\leq nq$). Let $(\sigma_i)_{i\leq \alpha},(\tau_j)_{j\leq\beta}$ be the non-zero singular values of $X,B$ where $rank(X)=\alpha,rank(B)=\beta$. The non-zero singular values of $X\bigotimes B^T$ are the $(\sigma_i\tau_j)_{i,j}$. Then the condition is $\alpha\beta=pr$. Note that $\beta\leq r,\alpha\leq p$. Necessarily $\beta=r,\alpha=p$ and then $p\leq n$.

Conclusion: The NSC is: $X,B$ have full rank and $p\leq n$.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer. I have a follow up question. What conditions need to be hold for $X$ and/or $B$ such that $XHB = 0$ iff $H=0$? (For example, for strict convexity for $B$, we need $A^TX^TXA$ to be invertible.) $\endgroup$
    – Mkl
    Jul 23, 2014 at 16:10
0
$\begingroup$

Did you try the case $n=q=p=r=1$? Consider $Y=0$, $X=1$, $(A,B) = (1,0),$ $(1/2, 1/2)$ and $(0,1)$. Yes, I know you said $r < \min(p,q)$, but you can easily throw in some irrelevant dimensions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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