0
$\begingroup$

Given $A,B\in\mathbb R^{n\times n}$ such that there is an $U\in\mathbb R^{n\times n}$ with $UU'=I$ and $UAU'=B$.

  1. Suppose each entry of $V$ is within $\pm\epsilon$ of each entry of $U$ is there a way to bound $$\|VAV'-B\|_2^2?$$

  2. Suppose we can create a matrix $\widehat B$ such that each entry of $B$ can be modified (added or multiplied) by some polynomial of $\epsilon$ (we can have different polynomial for each entry of $B$) then for what choices of functions can we get minimum in expectation of $$\|VAV'-\widehat B\|_2^2?$$

Improve this question
$\endgroup$
3
  • $\begingroup$ For 1., would you be content with a bound for Frobenius norm? $\endgroup$
    – Mark L. Stone
    Commented Apr 23, 2018 at 18:17
  • $\begingroup$ Frobenius norm would help. $\endgroup$
    – Turbo
    Commented Apr 23, 2018 at 18:21
  • $\begingroup$ You could numerically globally maximize the Frobenius norm, subject to element-wise bound constraints on V. For instance, using YALMIP's bmibnb global optimizer, in the most rudimentary specification, V = sdpvar(n,n,'full'); optimize([-epsilon <= V(:) - U(:) <= epsilon,-norm(VAV' - B,'fro'),sdpsettings('solver'','bmibnb')) . You could use the BARON solver instead, in this case by changing 'bmibnb' to 'baron'. You can specify relative and absolute optimality gaps which control how tightly the global optimum is found. Bigger gap, which can be found easier, means the bound isn't as tight. $\endgroup$
    – Mark L. Stone
    Commented Apr 23, 2018 at 19:04

1 Answer 1

Reset to default
3
$\begingroup$

Let $V = U + E$, and take $\epsilon \ge 0$. Then using $\|U\|_2 =1$ and $\|E\|_2 \le n\epsilon$, and applying triangle and submultiplicative inequaliies, we have

$\|VAV'-B\|_2 = \|EAU' + UAE' + EAE'\|_2 \le 2\|E\|_2\|A\|_2 + \|E\|_2^2\|A|| \le (2n\epsilon + n^2\epsilon^2)\|A\|_2$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .