Matrix Randomization Methods
This chapter presents algorithms for uniform matrix sample generation in norm-bounded sets. First, we discuss the simple case of matrix sampling in sets defined by ℓ p Hilbert–Schmidt norm, which reduces to the vector ℓ p norm randomization problem. Subse
- PDF / 372,950 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 236 Views
Matrix Randomization Methods
In this chapter we present algorithms for uniform matrix sample generation in norm bounded sets. First, we discuss the simple case of matrix sampling in sets defined by p Hilbert–Schmidt norm, which reduces to the vector p norm randomization problem. Subsequently we present an efficient solution to the more challenging problem of uniform generation in sets defined by the spectral norm. The algorithms presented here are available in [81, 83]. The reader interested in random generation of matrices with a Toeplitz structure may refer to [423].
18.1 Uniform Sampling in Hilbert–Schmidt Norm Balls As discussed in Sect. 17.1.1, the vectorization operation x = vec(X) defined in (3.8) reduces the p Hilbert–Schmidt matrix sample generation problem into an equivalent problem concerning vector samples. Therefore, the vector randomization algorithms presented in Chap. 16 can be used directly for the p Hilbert–Schmidt matrix sampling problem. A simple illustration of this idea is reported next for matrix generation in the Frobenius norm ball. Example 18.1 (Uniform matrices in the Frobenius norm ball) Suppose we are interested in generating samples of a real matrix X ∈ R2,3 uniformly distributed in the unit Frobenius norm ball, i.e. the 2 Hilbert–Schmidt norm ball B·2 R2,3 = X ∈ R2,3 : X2 ≤ 1 . Using the vectorization operator x = vec(X), we observe that this problem is equivalent to the generation of uniform random vectors in the 2 norm ball B·2 (R6 ), which can be easily performed by means of Algorithm 16.1. Next, we discuss uniform generation of matrix samples in the p induced norm balls, for p = 1 and p = ∞. R. Tempo et al., Randomized Algorithms for Analysis and Control of Uncertain Systems, Communications and Control Engineering, DOI 10.1007/978-1-4471-4610-0_18, © Springer-Verlag London 2013
267
268
18
Matrix Randomization Methods
18.2 Uniform Sampling in 1 and ∞ Induced Norm Balls The algorithm for matrix sample generation in the 1 induced norm ball follows directly from Corollary 17.1. That is, to generate a matrix X ∈ Rn,m with uniform distribution in B|·|1 (Rn,m ), it suffices to generate its columns independently and uniformly in the 1 vector norm ball B·1 (Rm ) using Algorithm 16.1. The complex case follows from direct application of Corollary 17.2, and hence Algorithm 16.4 can be used for random generation. Similarly, to generate a matrix sample X (real or complex) uniformly distributed in the ∞ induced norm ball B·∞ (Fn,m ), it suffices to generate XT (or X∗ , in the complex case) uniformly in the 1 induced norm ball B·1 (Fm,n ). We now discuss the problem of uniform generation in the spectral norm ball, which turns out to be technically more difficult than the cases previously considered. This difficulty is mainly due to the special structure of the spectral norm, which depends on the entries of the matrix only through an implicit relation given by the singular value decomposition. In Sect. 18.3 we present several sampling schemes based on rej
Data Loading...
