A sketching algorithm is a way to solve an optimization problem approximately and in a fraction of the usual time. We consider classical sketching algorithms which first compress data by multiplication with a random matrix. Our work improves and extends the paradigm, in which sketch matrices are optimized to yield better expected performance. This technique has only been used for a suboptimal variant of sketched low-rank decomposition (LRD). Our work extends the problem coverage to optimal sketched LRD, least…