The purpose of this two-part series is to provide a robustness analysis framework for a class of problems with highly structured modeling uncertainties. This framework is more general than that of the usual block, diagonally structured uncertainties, and it corresponds to a structure consisting of block-by-block matrix perturbations. We study the structured singular value with respect to this structure, and we establish a number of novel results for this notion. Specifically, Part I contains a study on the properties of the structured singular value, We give an alternative characterization of this notion as the solution of a smooth optimization problem. Furthermore, we show that under a certain circumstance the structured singular value reduces to a vector-induced matrix norm. Part II then addresses computational issues associated with the structured singular value. Our results are useful in that they not only extend the previous work but also provide both new insights and an improved computational method for this class of problems.