Probability and Statistics Seminar: Resilience of the rank of random matrices

Friday, January 24 at 3:30pm to 4:30pm

This is a past event.

Kaprielian Hall (KAP), 414
3620 South Vermont Avenue, Los Angeles, CA 90089

Asaf Ferber, UC Irvine    

Abstract: Let M be an n × m matrix of independent Rademacher (±1) random variables. It is well known that if n ≤ m, then M is of full rank with high probability. We show that this property is resilient to adversarial changes to M. More precisely, if m ≥ n+n^{1-ε}, then even after changing the sign of (1 − ε)m/2 entries, M is still of full rank with high probability. Note that this is asymptotically best possible as one can easily make any two rows proportional with at most m/2 changes. Moreover, this theorem gives an asymptotic solution to a slightly weakened version of a conjecture made by Van Vu.

Joint work with Kyle Luh and Gwen McKinley.

Event Type

Lecture / Talk / Workshop


University Park Campus

Add this to your calendar

Recent Activity