Dealing with the curse of dimensionality in systems and control: The randomization paradigm

Randomized algorithms have gained increasing popularity in the systems and control community for their ability of dealing in an efficient way with complex systems affected by uncertainty. In particular, at the expense of accepting a predetermined risk of failure, they allow to cope with the complexity/conservatism barriers of classical robust control and optimization methods. In this tutorial paper, we first briefly overview the main results for addressing probabilistic robust optimization problems using a randomized approach, in particular focusing on recent results that allow iterative and distributed implementations. Then, we show how the use of randomization proved to be a key tool in the development of distributed schemes for the solution of problems involving large amounts of data, as the well-known Google PageRank problem. Finally, we overview theoretical computer science and numerical linear algebra approaches for the solution of least-squares problems and low-rank matrix approximations, for the case when the matrices involved are of very large scale. These results, which go under the name of randomized matrix algorithms, may prove very useful in the context of systems estimation and control.