Back to Math

Optimal probe distribution for Girard–Hutchinson

max⁡A∈SE ⁣[(∑iyi∗Ayi)2]≥max⁡A∈SE ⁣[(∑ixi∗Axi)2]=n2⋅max⁡A∈SE tr⁡ ⁣(X‾∗AX‾)2 \max_{A\in S}\mathbb{E}\!\left[\left(\sum_i y_i^*Ay_i\right)^2\right] \ge \begin{aligned} &\max_{A\in S}\mathbb{E}\!\left[\left(\sum_i x_i^*Ax_i\right)^2\right] \\ &{}=n^2\cdot\max_{A\in S}\mathbb{E}\,\operatorname{tr}\!\left(\overline{X}^{*}A\overline{X}\right)^2 \end{aligned}
Y‾:=[y1 ⋯ yk]X‾:=X/n \begin{aligned} \overline{Y}&:=[y_1\ \cdots\ y_k] \\ \overline{X}&:=X/\sqrt{n} \end{aligned}
max⁡A∈SE ⁣[(∑iyi∗Ayi)2]=max⁡A∈Smax⁡U∈U(n)E tr⁡ ⁣(Y‾∗U∗AUY‾)2=max⁡A∈Smax⁡U∈U(n)E tr⁡ ⁣(R∗Q∗U∗AUQR)2=max⁡A∈Smax⁡U∈U(n)E tr⁡ ⁣(R∗(UQ∗)A(UQ)R)≥max⁡A∈SE(Q,R)U′∼Unif⁡(U(n))tr⁡ ⁣(R∗(U′Q)∗A(U′Q)R)2=max⁡A∈SE tr⁡ ⁣(R∗(U′Q)∗A(U′Q)R)2=max⁡A∈SE tr⁡ ⁣(R∗X‾∗AX‾R)2=max⁡A∈SEX∼Unif⁡(U(n,k))W∼Unif⁡(U(k))Rtr⁡ ⁣(R∗W∗X‾∗AX‾WR)2=max⁡A∈SEX‾ER,W tr⁡ ⁣(X‾∗AX‾WRR∗W∗)2 \begin{aligned} &\max_{A\in S}\mathbb{E}\!\left[\left(\sum_i y_i^*Ay_i\right)^2\right] \\ &{}=\max_{A\in S}\max_{U\in U(n)}\mathbb{E}\,\operatorname{tr}\!\left(\overline{Y}^{*}U^{*}AU\overline{Y}\right)^2 \\ &{}=\max_{A\in S}\max_{U\in U(n)}\mathbb{E}\,\operatorname{tr}\!\left(R^{*}Q^{*}U^{*}AUQR\right)^2 \\ &{}=\max_{A\in S}\max_{U\in U(n)}\mathbb{E}\,\operatorname{tr}\!\left(R^{*}(UQ^{*})A(UQ)R\right) \\ &{}\ge\max_{A\in S}\mathbb{E}_{\substack{(Q,R)\\U'\sim\operatorname{Unif}(U(n))}}\operatorname{tr}\!\left(R^{*}(U'Q)^{*}A(U'Q)R\right)^2 \\ &{}=\max_{A\in S}\mathbb{E}\,\operatorname{tr}\!\left(R^{*}(U'Q)^{*}A(U'Q)R\right)^2 \\ &{}=\max_{A\in S}\mathbb{E}\,\operatorname{tr}\!\left(R^{*}\overline{X}^{*}A\overline{X}R\right)^2 \\ &{}=\max_{A\in S}\mathbb{E}_{\substack{X\sim\operatorname{Unif}(U(n,k))\\W\sim\operatorname{Unif}(U(k))\\R}}\operatorname{tr}\!\left(R^{*}W^{*}\overline{X}^{*}A\overline{X}WR\right)^2 \\ &{}=\max_{A\in S}\mathbb{E}_{\overline{X}}\mathbb{E}_{R,W}\,\operatorname{tr}\!\left(\overline{X}^{*}A\overline{X}WRR^{*}W^{*}\right)^2 \end{aligned}

Absorbtion 1: if UU unif random unitary and Q,MQ,M w/ QQ orth cols, then UQUQ is unif and orth cols and UQ⊥ ⁣ ⁣ ⁣⊥MUQ \perp\!\!\!\perp M.

Absorbtion 2: if VV is unif and orth col and WW is unitary, then W∼Unif⁡(n,k)W\sim\operatorname{Unif}(n,k)

1kE tr⁡ Y‾∗AY‾=tr⁡A \frac{1}{k}\mathbb{E}\,\operatorname{tr}\,\overline{Y}^{*}A\overline{Y}=\operatorname{tr}A
1kE tr⁡ ⁣(R∗Q∗AQR)=tr⁡A \frac{1}{k}\mathbb{E}\,\operatorname{tr}\!\left(R^{*}Q^{*}AQR\right)=\operatorname{tr}A
tr⁡ E R∗Q∗AQR=ktr⁡A \operatorname{tr}\,\mathbb{E}\,R^{*}Q^{*}AQR=k\operatorname{tr}A
tr⁡ EU∼Unif⁡(U(n))EQ,R ⁣[R∗Q∗U∗AUQR] \operatorname{tr}\,\mathbb{E}_{U\sim\operatorname{Unif}(U(n))}\mathbb{E}_{Q,R}\!\left[R^{*}Q^{*}U^{*}AUQR\right]
tr⁡ ER R∗EX‾ ⁣(X‾∗AX‾)R=tr⁡ E R∗ ⁣(tr⁡AnI)R \operatorname{tr}\,\mathbb{E}_{R}\,R^{*}\mathbb{E}_{\overline{X}}\!\left(\overline{X}^{*}A\overline{X}\right)R =\operatorname{tr}\,\mathbb{E}\,R^{*}\!\left(\frac{\operatorname{tr}A}{n}I\right)R
tr⁡An⋅tr⁡ E R∗R=ktr⁡A \frac{\operatorname{tr}A}{n}\cdot\operatorname{tr}\,\mathbb{E}\,R^{*}R=k\operatorname{tr}A