Conservatism of randomized structured singular value

In this note, we study the conservatism of structured singular value computation by a randomized algorithm. It is proved that, if the maximization problem μ(M) = max ρ (MΔ) is solved by generating polynomial number of random Δ samples and then taking the maximum of the function at these sample points, for any fixed lower bound on the confidence level, conservatism of the resulting estimate grows faster than any polynomial function of the logarithm of the matrix size. This result holds for purely complex, mixed, and purely real cases with no repeated blocks. However, it is shown to be not true if the number of samples exceeds some exponential function for the purely complex version of the problem. Although the estimate obtained by polynomial number of samples can be used to find an exact robustness margin with a high confidence level, for all except for a small relative volume of the uncertainty set, it has high conservatism for the worst-case robustness analysis, no matter how small the confidence level lower bound may be. The results of this note imply that conservatism will be large for certain classes of matrices. However, this does not eliminate the possibility of existence of other classes of matrices for which the conservatism is small.