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$
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$.

| cite | improve this answer | |
$\endgroup$
  • $\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 '14 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.

| cite | improve this answer | |
$\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.