M. Rudelson

activity

19962026

most citedDelocalization of eigenvectors of random matrices with independent entries

40 citations · 249 across the 41 of their papers we have counts for

collaborators

49 papers

math.PR2026

Well-invertible column subsets of sparse matrices are rare

Han Huang, Mark Rudelson, Konstantin Tikhomirov

A random $n \times k$ matrix $S$ is an \emph{ $(r, α)$ -oblivious subspace injection} (OSI) if $E ∥ S^{⊤} x ∥_{2}^{2} = ∥ x ∥_{2}^{2}$ for every $x \in R^{n}$ , and for every fixed…

cs.DS2026

Well-Conditioned Oblivious Perturbations in Linear Space

Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1

Perturbing a deterministic $n$ -dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the co…

math.FA2026

Hardness of approximation of centered convex bodies by polytopes

Han Huang, Mark Rudelson

The distance between convex bodies $K, L \subseteq \R^n$ is defined as \[ d(K,L)= \inf \left\{ λ\ge 1: \ L-x \subseteq T (K-y) \subseteq λ(L-x) \right\}, \] where the infimum is…

cs.DS2023★ 6 cited

Optimal Embedding Dimension for Sparse Subspace Embeddings

Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1

A random $m \times n$ matrix $S$ is an oblivious subspace embedding (OSE) with parameters $ε > 0$ , $δ \in (0, 1/3)$ and $d \leq m \leq n$ , if for any $d$ -dimensional subspace $W\subseteq R…

math.PR2022

Approximately Hadamard matrices and Riesz bases in random frames

Xiaoyu Dong, Mark Rudelson

An $n \times n$ matrix with $\pm 1$ entries which acts on $R^{n}$ as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining num…

math.MG2021

A quick estimate for the volume of a polyhedron

Alexander Barvinok, Mark Rudelson

Let $P$ be a bounded polyhedron defined as the intersection of the non-negative orthant $R_{+}^{n}$ and an affine subspace of codimension $m$ in $R^{n}$ . We show that a sim…