Stat is tical Randomized Learning Theory and Algorithms for Control

he topic of the present article is the use of randomized algo- T rithms to solve some problems in control system design that are perceived to be “difficult. ” The aim is to give a tutorial intro-duction to the subject by giving just a flavor of the main issues and the randomized approach. More exhaustive (not to say exhaust-ing) descriptions of this approach will be presented elsewhere. The starting point of this study is a set of recently-proven re-sults on the complexity of controller analysis and synthesis prob-lems, which address the rate at which the difficulty of ‘ such problems “scales up ” as the order or the dimension of the plant and/or controller increases. It can be shown that several in-nocuous-looking problems in matrix and control system analysis are “intractable ” in a very specific technical sense, to be de-scribed in the overview given in the next section. The set of such “intractable ” problems includes very natural problems such as the stability, norm-boundedness and nonsingularity of so-calle