12 problems

Improved-constant conjecture. The stated probability bound holds for the randomized subspace approximation setting under the hypotheses of the CDF theorem.

Improved-factor conjecture. The factor $4^k$ can be replaced by $2^k$, so that

Let $A$ be an $m\times n$ real matrix of rank $r$, and let $S\in\mathbb{R}^{s\times m}$ be an oblivious sketching matrix. Write $\sigma_{\max}(A)$ and $\sigma_{\min}(A)$ for the la…

Let $\sigma_1\geq\sigma_2\geq\cdots$ be the singular values relevant to the low-rank approximation problem, let $k$ be the target rank, and let $b$ be the block size with…

Let $m$ be the sampling number, let $\lambda=\lVert A\rVert_2$ and $\phi=\lVert A\rVert_F$ for a symmetric matrix $A$, and let $\varepsilon_{\mathrm{abs}}$ be the threshold appeari…

Let $m$ be the sampling number, let $mu=r_{\mathrm{eff}}(A)$ for a nonzero symmetric positive semidefinite matrix $A$, and let $\varepsilon_{\mathrm{rel}}$ be the threshold appeari…

Rank-preservation conjecture. The rank requirement for a valid preconditioner holds with exponentially-high probability for suitable SASOs and for SRFTs.

Let $Q_T$ be a Kac walk of length $T$ on $\operatorname{SO}(d)$, obtained by composing random coordinate-plane rotations. Given a set of $n$ points in $\mathbb{R}^{d}$ and an error…

Let $\boldsymbol{A}$ be a matrix, let $\boldsymbol{A}_k$ be its best rank-$k$ approximation, and let $\boldsymbol{U}_k$ contain the top-$k$ left singular vectors of…

Let $\boldsymbol{A}$ be a positive semidefinite matrix with eigenvalues $\sigma_1\geq\cdots\geq\sigma_n\geq0$, let $\boldsymbol{U}_k$ contain its top-$k$ eigenvectors, and let $p$…

Let a block Kaczmarz method update an iterate using a block containing many rows of the system matrix, and let a projection update enforce consistency with the corresponding null-s…

Let $A$ be a matrix with numerical rank $\rho$ and let $\rho_+$ be a reasonably small upper bound for $\rho$. Let $G$ be a random matrix used to compute an approximate basis for a…