Norm of sum of shifted outer products

226 Views Asked by At

Consider two vectors $u, v \in \mathbb{R}^m$ satisfying $\| u \|_2 = \| v \|_2 = 1$ and $\#\mathrm{supp}(v) \leq n < m$, where $\mathrm{supp}$ denotes the support of the vector (i.e. locations of nonzero coordinates). Additionally, assume that $\mathrm{supp}(u) = \mathrm{supp}(v)$. Assume that $u^i$ denotes the left-circular shift of $u$ by $i$ locations, i.e.

$$ u = (u_1, \dots, u_n, 0, \dots, 0) \Rightarrow u^1 = (0, u_2, \dots, u_n, 0 \dots, u_1) $$

Form the following matrix:

$$ X = u v^\top + u^1 {v^1}^\top + \dots + u^{m-1} {v^{m-1}}^\top $$

Question: I want to obtain a nontrivial bound on the operator and Frobenius norms of this matrix. The only bound that I was able to obtain so far is using the subadditivity of the Frobenius norm and the fact that $\| u_i v_i^\top \|_F = 1, \; \forall i.$ $$ \| X \|_{\mathrm{op}} \leq \| X \|_F \leq m \| u_i v_i^\top \| = m $$

Any ideas or pointers to references are more than welcome.