1

Say that we have the following matrices: $A\in M_{n,n}$ which is unknown, $Y\in M_{n,m}/\{0_{n,m}\}$ and $X\in M_{n,m}/\{0_{n,m}\}$. I want to show that the following set is convex $\Omega=\{S\in M_{m,m},\space S=(Y-A\times X)^T(Y-A\times X)\space \space |\space \space\|A\|_2\leq \frac{\epsilon}{n}\}$.

From the norm equivalence we have $\|A\|_2\leq \|A\|_1 \leq n\|A\|_2$ we have only n this is because A is a square matrix of dimension n and so $n=m$. What I would like to have as a constraint is $\|A\|_1\leq \epsilon$ but this will make the set a polygon having parabolas for each side which not convex.. so if we assume that $\|A\|_2\leq \frac{\epsilon}{n}$, then $\|A\|_1\leq \epsilon$. I'm considering $\|A\|_2 \leq \frac{\epsilon}{n}$ because the set would be convex and smaller than considering $\|A\|_1\leq \epsilon$ which is not convex.

So how can we prove that $\Omega$ is a convex set?

user2987
  • 761
  • When writing $A\times X$ and $\times AX$, do you simply mean the product $AX$? – Julien Feb 13 '13 at 00:42
  • I think that I did a typo here – user2987 Feb 13 '13 at 00:43
  • I have only the expression of $A\times X$ which is the regular matrix product AX. – user2987 Feb 13 '13 at 00:44
  • Note that $A$ should not be given at the beginning. It ranges over all matrices which satisfy the constraint. Also, if you know the value of $\epsilon$ you should give it. Otherwise, you might as well replace $\epsilon/n$ by $\epsilon$. – Julien Feb 13 '13 at 00:54
  • What is $X$? What is its relationship to $\epsilon/n$? If $S$ is convex for arbitrary $X$, then the unconstrained $S$ is also convex, since you can simultaneously rescale $A$ and $X$. – user7530 Feb 13 '13 at 01:43
  • Actually $A$ is not given here that's why we put the constraint on $|A|_2$ and $\epsilon$ is nothing but a sufficiently small number and n is given as mentioned above to be the dimension of A. More specifically the constraint comes from the norm equivalence where $n=m$ and another constraint $|A|_1\leq \epsilon$.. – user2987 Feb 13 '13 at 01:59
  • Again, if you don't say more on $\epsilon$ it does not make much sense to write $\epsilon/n$ rather than simply $\epsilon$. – Julien Feb 13 '13 at 02:12
  • 1
    Your claim that "without the constraint, the set is not convex" is not true if $X=0$. In this case, your set is a singleton, hence convex. – Julien Feb 13 '13 at 02:25
  • I just made some changes to explain more about $\epsilon$. – user2987 Feb 13 '13 at 02:45
  • Larger? Actually $\Omega\subseteq {bla||A|_1\leq \epsilon}$. – Julien Feb 13 '13 at 02:52
  • Yes sorry that was a typo again actually I'm trying to look for a solution inside this set that's why I want to make it smaller and I would like to make sure about the convexity.. – user2987 Feb 13 '13 at 03:01
  • And if we set $X=0$ does not have sense because we loose any dependance on $A$. – user2987 Feb 13 '13 at 03:09
  • Yes, it makes sense. If you want $X\neq 0$, you have to say it in your question. – Julien Feb 13 '13 at 03:12
  • Yes we should have $X$ different from $0$. – user2987 Feb 13 '13 at 03:15

0 Answers0