Mathematical Sciences Research Institute

Home » Workshop » Schedules » The smallest singular value of a $d$-regular random square matrix

The smallest singular value of a $d$-regular random square matrix

Geometric functional analysis and applications November 13, 2017 - November 17, 2017

November 17, 2017 (09:30 AM PST - 10:30 AM PST)
Speaker(s): Alexander Litvak (University of Alberta)
Location: MSRI: Simons Auditorium
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC



We derive a lower bound on the smallest singular value of a random $d$-regular matrix, that is, the adjacency matrix of a random $d$-regular directed graph. More precisely, let $C_1<d< c_1 n/\log^2 n$ and let $M$ be uniformly distributed on the set of all $0/1$-valued $n\times n$ matrices such that each row and each column of a matrix has exactly $d$ ones. Then the smallest singular value $s_{n} (M)$ of $M$ is greater than $c_2 n^{-6}$ with probability at least $1-C_2\log^2 d/\sqrt{d}$, where $c_1$,  $c_2$, $C_1$, and $C_2$ are absolute positive constants. This is a joint work with A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef

30104?type=thumb Litvak Notes 1.03 MB application/pdf Download
Video/Audio Files


H.264 Video 17-Litvak.mp4 319 MB video/mp4 rtsp://videos.msri.org/data/000/030/029/original/17-Litvak.mp4 Download
Troubles with video?

Please report video problems to itsupport@msri.org.

See more of our Streaming videos on our main VMath Videos page.