Probabilistic Analysis of the Grassmann Condition Number

Abstract

We analyze the probability that a random m-dimensional linear subspace of $\mathbb{R}^{n}$ both intersects a regular closed convex cone $C\subseteq\mathbb{R}^{n}$ and lies within distance α of an m-dimensional subspace not intersecting C (except at the origin). The result is expressed in terms of the spherical intrinsic volumes of the cone C. This allows us to perform an average analysis of the Grassmann condition number for the homogeneous convex feasibility problem ∃x∈C∖0:Ax=0. The Grassmann condition number is a geometric version of Renegar’s condition number, which we have introduced recently in Amelunxen and Bürgisser (SIAM J. Optim. 22(3):1029–1041 (2012)). We thus give the first average analysis of convex programming that is not restricted to linear programming. In particular, we prove that if the entries of $A\in\mathbb {R}^{m\times n}$ are chosen i.i.d. standard normal, then for any regular cone C, we have . The proofs rely on various techniques from Riemannian geometry applied to Grassmann manifolds.

Appendices

Appendix A: Averaging the Twisted Characteristic Polynomial

Recall the setting of Sect. 4.2. Let $A\in\mathbb{R}^{k\times k}$ and $\varphi\colon\mathbb{R} ^{k}\to\mathbb{R} ^{k},x\mapsto Ax$. Using the notation $\operatorname{ch}_{\ell}(A,t) = \operatorname{ch}_{Y_{0}}(\varphi,t)$, where $Y_{0} =\mathbb{R} ^{\ell}\times0$, we have

$$ \underset{Y}{\mathbb{E}} \bigl[ \operatorname{ch}_Y( \varphi ,t) \bigr] = \underset{Q}{\mathbb{E}} \bigl[ \operatorname{ch}_\ell \bigl(Q^{\mathrm{T}}A Q,t\bigr) \bigr] . $$

(A.1)

(The reason is that $QY_{0}\in\operatorname{Gr}_{k,\ell}$ is uniform random when Q∈O(k) is uniformly chosen at random.) This equality allows us to prove Theorem 4.1 with basic matrix calculus. The main idea is to use the multilinearity of the determinant and the invariance of the coefficients σ _i (A) under similarity transformations, to show that the coefficients of $\mathbb{E}[\operatorname{ch}_{\ell}(Q^{\mathrm{T}}AQ,t)]$ are linear combinations of the σ _i (A). We then compute the coefficients of these linear combinations by choosing for A scalar multiples of the identity matrix.

In the following, we use the notation [k]:={1,…,k}, and we denote by $\binom{[k]}{i}$ the set of all i-element subsets of [k]. For $A\in\mathbb{R}^{k\times k}$ and $J\in\binom {[k]}{i}$, we denote by $\operatorname{pm}_{J}(A) := \det(A_{J})$ the Jth principal minor of A, where A _J denotes the submatrix of A obtained by selecting the rows and columns of A whose indices lie in J. It is well known (cf. for example [28, Theorem 1.2.12]) that σ _i (A) is the sum of all principal minors of A of size i, i.e.,

$$ \sigma_i(A) = \sum_{J\in\binom{[k]}{i}} \operatorname{pm}_J(A) . $$

(A.2)

For 0≤ℓ≤k, the ℓth leading principal minor $\operatorname{lpm}_{\ell}(A) := \operatorname{pm}_{[\ell]}(A)$ is defined as the principal minor for J=[ℓ]. Note that $\operatorname{lpm}_{\ell}(A) = \det_{\mathbb {R}^{\ell}\times 0}(\varphi)$.

Lemma A.1

Let $A\in\mathbb{R}^{k\times k}$, and let Q∈O(k) be chosen uniformly at random. Then, for all , we have

$$ \underset{Q}{\mathbb{E}} \bigl[\operatorname{pm}_J \bigl(Q^{\mathrm{T}} A Q\bigr) \bigr] = \underset{Q}{\mathbb{E}} \bigl[ \operatorname{lpm}_\ell\bigl(Q^{\mathrm{T}} A Q\bigr) \bigr] = \frac{1}{\binom{k}{\ell}} \sigma_\ell(A) . $$

Proof

For the first equality let J={j ₁,…,j _ℓ }, j ₁<⋯<j _ℓ , and let π be any permutation of [k] such that π(i)=j _i for all i=1,…,ℓ. If M _π denotes the permutation matrix corresponding to π, i.e., M _π e _i =e _π(i), then $A_{J}=(M_{\pi}^{\mathrm{T}} A M_{\pi})_{[\ell]}$, and therefore $\operatorname{pm}_{J}(A)=\operatorname{lpm}_{\ell}( M_{\pi}^{\mathrm{T}} A M_{\pi})$. This implies

$$ \underset{Q}{\mathbb{E}} \bigl[\operatorname{pm}_J \bigl(Q^{\mathrm{T}} A Q\bigr) \bigr] = \underset{Q}{\mathbb{E}} \bigl[ \operatorname{lpm}_\ell\bigl(M_\pi^{\mathrm{T}} Q^{\mathrm{T}} A Q M_\pi \bigr) \bigr] = \underset{Q}{\mathbb{E}} \bigl[\operatorname{lpm}_\ell\bigl(Q^{\mathrm{T}} A Q\bigr) \bigr] , $$

where we have used the fact that right multiplication by the fixed element M _π leaves the uniform distribution on O(k) invariant. This implies

which was to be shown. □

Proof of Theorem 4.1

Statement (4.4) follows from (A.1) and Lemma A.1.

For proving (4.5), we start with a general observation. By multilinearity, we write the determinant of a matrix with columns v ₁,…,v _i−1,v _i +α⋅e _i ,v _i+1,…,v _n in the form

$$\begin{aligned} &\det(v_1,\ldots,v_{i-1},v_i+\alpha e_i,v_{i+1},\ldots,v_n)\\ &\quad{}= \det(v_1,\ldots,v_n) + \alpha\det(v_1,\ldots,v_{i-1},e_i, v_{i+1},\ldots,v_n) . \end{aligned}$$

Using this repeatedly, we obtain

$$ \det\bigl(A+\operatorname{diag}(\alpha_1,\ldots, \alpha_n)\bigr) = \sum_{J\subseteq[k]} \operatorname{pm}_J(A)\cdot\prod_{i\in[k]\setminus J} \alpha_i . $$

(A.3)

By (4.3) we can express the twisted characteristic polynomial as

$$\operatorname{ch}_\ell(A,t) =t^{k-\ell}\cdot\det\bigl(A+ \operatorname {diag}(-t,\ldots ,-t,1/t,\ldots,1/t)\bigr) . $$

Applying (A.3), we expand this to obtain

$$ \operatorname{ch}_\ell(A,t) = \sum _{J\subseteq[k]} (-1)^{c_1(J)}\cdot \operatorname{pm}_J(A) \cdot t^{c_2(J)} , $$

(A.4)

where $c_{1},c_{2}\colon2^{[k]}\to\mathbb{N}$ are some integer-valued functions on the power set of [k]. Averaging the twisted characteristic polynomial with the help of Lemma A.1 yields

$$\begin{aligned} \underset{Q}{\mathbb{E}} \bigl[\operatorname{ch}_\ell \bigl(Q^{\mathrm{T}} A Q,t\bigr) \bigr] & = \sum_{J\subseteq[k]} (-1)^{c_1(J)}\cdot \underset{Q}{\mathbb{E}} \bigl[\operatorname{pm}_J \bigl(Q^{\mathrm{T}} A Q\bigr) \bigr]\cdot t^{c_2(J)} \\ &{} = \sum_{J\subseteq[k]} \frac{(-1)^{c_1(J)}}{\binom{k}{|J|}}\cdot \sigma_{|J|}(A) t^{c_2(J)} = \sum_{i,j=0}^k \tilde{d}_{ij}\cdot\sigma_{k-j}(A)\cdot t^{k-i} , \end{aligned}$$

for some rational constants $\tilde{d}_{ij}$. It remains to prove that the $\tilde{d}_{ij}$ coincide with the d _ij defined in Theorem 4.1.

To compute the $\tilde{d}_{ij}$, we choose A=sI _k . Then, $\operatorname{ch}_{\ell}(s I_{k},t) = (s-t)^{\ell}\cdot(1+s t)^{k-\ell}$. Since , and Q ^T sI _k Q=sI _k , we get

$$ (s-t)^\ell\cdot(1+s t)^{k-\ell} = \operatorname{ch}_\ell(s I_k,t) = \underset{Q}{\mathbb{E}} \bigl[\operatorname{ch}_\ell \bigl(Q^{\mathrm{T}} s I_k Q,t\bigr) \bigr] = \sum _{i,j=0}^k \tilde{d}_{ij} \binom{k}{j} s^{k-j} t^{k-i} . $$

Let us expand the first term:

$$ \begin{aligned}[b] (s-t)^\ell\cdot(1 + s t)^{k-\ell} & = \left(\sum_{\lambda=0}^\ell\binom{\ell}{\lambda} (-1)^{\ell -\lambda} s^\lambda t^{\ell-\lambda}\right)\cdot \left(\sum_{\mu=0}^{k-\ell} \binom{k-\ell}{\mu} s^\mu t^\mu \right) \\ &{} = \sum_{\lambda=0}^\ell\sum_{\mu=0}^{k-\ell} (-1)^{\ell -\lambda} \binom{\ell}{\lambda} \binom{k-\ell}{\mu} s^{\lambda+\mu} t^{\ell-\lambda+\mu} \\ &\!\!\!\!\!\!\!\!\!\!\!\!\! {}\stackrel{\substack{i=k-\ell+\lambda-\mu\\ j=k-\lambda-\mu}}{=} \sum_{\substack{i,j=0\\i+j+\ell\equiv0\\\pmod{2}}}^k (-1)^{\frac{i-j}{2}-\frac{\ell}{2}}\binom{\ell}{\frac {i-j}{2}+\frac{\ell}{2}} \binom{k-\ell}{k-\frac{i+j+\ell}{2}} s^{k-j} t^{k-i} , \end{aligned} $$

(A.5)

where again we interpret $\binom{n}{m}=0$ if m<0 or m>n, i.e., the above summation over i, j in fact only runs over the rectangle determined by the inequalities $0\leq\frac{i-j}{2}+\frac{\ell}{2}\leq\ell$ and $0\leq k-\frac{i+j+\ell}{2}\leq k-\ell$. (See Fig. 1 for an illustration of the change of summation.) Note that the reverse substitution is given by $\lambda=\frac {i-j+\ell}{2}$ and $\mu=k-\frac{i+j+\ell}{2}$.

Fig. 1

Illustration of the change of summation in (A.5) (k=8, ℓ=5)

Comparing the coefficients of the above two expressions for (s−t)^ℓ⋅(1+st)^k−ℓ reveals that indeed $\tilde{d}_{ij}=d_{ij}$ as defined in Theorem 4.1. This completes the proof of (4.5).

For the last claim (4.6) in Theorem 4.1, we define the positive characteristic polynomial

$$ \operatorname{ch}_\ell^+(A,t) = \det \left(\begin{array}{c@{\quad}c} A_1+tI_\ell& A_2 \\ tA_3 & tA_4+I_{k-\ell} \end{array}\right) $$

by replacing −t by t in (4.3). By the same reasoning as for (A.4), we get

$$ \operatorname{ch}^+_\ell(A,t) = \sum_{J\subseteq[k]} \operatorname {pm}_J(A)\cdot t^{c_2(J)} , $$

(A.6)

with the same function $c_{2}\colon2^{[k]}\to\mathbb{N}$ as in (A.4). Moreover, by arguing as in the proof of (4.5) before, we show that

$$ \underset{Q}{\mathbb{E}} \bigl[\operatorname{ch}^+_\ell \bigl(Q^{\mathrm{T}}AQ,t\bigr) \bigr] = \sum_{i,j=0}^k |d_{ij}|\cdot\sigma_{k-j}(A)\cdot t^{k-i} . $$

(A.7)

Now assume that A is positive semidefinite. Then each of its principal minors is nonnegative, i.e., $\operatorname{pm}_{J}(A)\geq0$ for all J⊆[k]. Therefore, if t≥0, we get from (A.4) and (A.6) that

$$ \bigl|\operatorname{ch}_\ell(A,t)\bigr| = \biggl| \sum_{J\subseteq[k]} (-1)^{c_1(J)}\cdot\operatorname {pm}_J(A)\cdot t^{c_2(J)} \biggr| \leq\sum_{J\subseteq[k]} \operatorname{pm}_J(A)\cdot t^{c_2(J)} = \operatorname{ch}^+_\ell(A,t) . $$

Taking into account (A.7) completes the proof of Theorem 4.1. □

Appendix B: Proof of Some Technical Estimations

Recall that the symbol  is used to mark simple estimates, which are easily checked with a computer algebra system.

Proof of Lemma 5.2

(1) We make a case distinction by the parity of ℓ. Using Γ(x+1)=x⋅Γ(x), for odd ℓ we obtain

$$ \frac{\varGamma(\frac{m+\ell+1}{2})}{\varGamma(\frac{m}{2})} = \prod_{a=0}^{\frac{\ell-1}{2}} \biggl( \frac{m}{2}+a \biggr) \leq\frac{m}{2}\cdot \biggl(\frac{m+\ell-1}{2} \biggr)^{\frac{\ell-1}{2}} \leq\sqrt{\frac{m}{2}}\cdot \biggl(\frac{m+\ell}{2} \biggr)^{\frac {\ell}{2}} . $$

Using additionally $\varGamma(x+\frac{1}{2})<\sqrt{x}\cdot\varGamma(x)$, for even ℓ we get

$$ \frac{\varGamma(\frac{m+\ell+1}{2})}{\varGamma(\frac{m}{2})} = \prod_{a=0}^{\frac{\ell}{2}-1} \biggl(\frac{m+1}{2}+a \biggr) \cdot\frac{\varGamma(\frac{m+1}{2})}{\varGamma(\frac{m}{2})} < \biggl( \frac{m+\ell}{2} \biggr)^{\frac{\ell}{2}}\cdot\sqrt {\frac{m}{2}} . $$

(2) As for the second estimate, we distinguish the cases i≥2k and i≤2k. From 0≤k≤m−1 and 0≤i−k≤n−m−1, we get

$$\begin{aligned} 1 \leq& m-k+i-k \leq n-1 , \\ 1 \leq& n-(m-k+i-k) \leq n-1 . \end{aligned}$$

For i≥2k we thus have

$$ \biggl(\frac{m+i-2k}{n-m-i+2k} \biggr)^{\frac{i-2k}{2}} \leq(n-1)^{\frac{i-2k}{2}} < n^{\frac{i}{2}} , $$

and for i≤2k

$$ \biggl(\frac{m+i-2k}{n-m-i+2k} \biggr)^{\frac{i-2k}{2}} = \biggl(\frac{n-m+2k-i}{m-2k+i} \biggr)^{\frac{2k-i}{2}} \leq(n-1)^{\frac{2k-i}{2}} < n^{\frac{i}{2}} . $$

(3) The I-functions have been estimated in [10, Lemma 2.2] in the following way. Let $\varepsilon:=\sin(\alpha)=\frac{1}{t}$. For i<n−2,

$$ I_{n,n-2-i}(\alpha) = \int_0^\alpha\cos(\rho)^{n-2-i}\cdot\sin (\rho)^i\,\mathrm{d}\rho \leq\frac{\varepsilon^{i+1}}{i+1} , $$

and for i=n−2, assuming n≥3,

With these estimates we obtain

For $\varepsilon<n^{-\frac{3}{2}}$ we thus get

Similarly, we derive

$$\sum_{i=0}^{n-2} \binom{n-2}{i} \cdot I_{n,n-2-i}(\alpha) < \varepsilon\cdot \biggl((1+\varepsilon)^{n-2} + \frac{1.4}{\sqrt{n}}\cdot\varepsilon^{n-2} \biggr) . $$

For $\varepsilon<\frac{1}{m}$ we thus have

which proves the assertion. □