1
$\begingroup$

Theorem 4.1 in Tropp's Matrix Concentration Inequalities provides an exponential concentration inequality for the spectral norm of a matrix $Z = \sum_i \gamma_i B_i $, where $\gamma_i$ are an i.i.d. sample of either standard normals or Rademacher random variables and $B_i$ are deterministic $d_1 \times d_2$ matrices.

Question: Are there similar bounds if we allow $\gamma_i$ to be the individual components of a vector $\gamma$ drawn uniformly at random from the unit sphere?

The question is motivated by a recent work in convolutional phase retrieval. Specifically, in [2], p. 2 mentions that a vector $x \in \mathbb{S}^{n-1}$ drawn uniformly from the unit sphere will satisfy $\left\| C_x \right\| = \mathcal{O}(\log n)$ in expectation, where $C_x$ is a partial random circulant matrix associated with $x$. It would be nice if one could quantify how likely it is that a draw $x \overset{\mathrm{unif}}{\sim} \mathbb{S}^{d-1} $ will result in a "bad" $\| C_x \|$.

Edit - a quick attempt: Given a circulant matrix $C \in \mathbb{R}^{n \times n}$ generated by a vector $a$, we may decompose it into the following sum:

$$ C = \sum_{i=0}^{n-1} a_i P^i, \; P = \begin{pmatrix} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots \\ 1 & 0 & 0 & \dots & 0 \end{pmatrix} $$

Combined with the fact that $\left( \frac{a_0}{\left\| a \right|}, \dots, \frac{a_{n-1}}{\left| a \right\|} \right) \overset{d}{=} \mathrm{Unif}(\mathbb{S}^{n-1})$ when $a \sim \mathcal{N}(0, I_{n})$, we could write

$$ C_a = \frac{1}{\left\| a \right\|} \left( \sum_{i=0}^{n-1} a_i P^i \right) $$

From there, if we observe that $\left\| a \right\| = \Theta(\sqrt{n})$ with high probability, it seems plausible that Tropp's bound for gaussian series and an appropriate sequence of union bounds could give us an exponential upper bound for $\| C_a \|$. I will update accordingly.

[1]: Tropp, Joel A. (2015). An introduction to matrix concentration inequalities. Foundations and Trends® in Machine Learning 8.1-2 (2015): 1-230

[2]: Qu, Q., Zhang, Y., Eldar, Y. C., & Wright, J. (2017). Convolutional phase retrieval via gradient descent. arXiv preprint arXiv:1712.00716.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.