Various Solutions for A^½ and A^–½

Let A=ΦΛΦ^T be the eigen-decomposition of the real, symmetric, positive definite nXn matrix A, where Φ and Λ are respectively the eigenvector and eigenvalue matrices of A. Here Λ=diag(λ₁,…,λ_n) is the diagonal eigenvalue matrix with λ₁≥…≥λ_n>0, and Φ∈ℜ^nXn is orthonormal. A solution for A^½ is L=ΦD, where D=. However, in general this is not a symmetric solution, and for any orthonormal¹ matrix U, ΦDU is also a solution. We can show that A^½ is symmetric if, and only if, it is of the form ΦDΦ^T, and there are 2ⁿ symmetric solutions for A^½. When D is positive definite, we obtain the unique symmetric positive definite solution for A^½ as ΦΛ^½Φ^T, where Λ^½ = . Similarly, a general solution for the inverse square root A^–½ of A is ΦD^–1U, where D is defined before and U is any orthonormal matrix. The unique symmetric positive definite solution for A^–½ is ΦΛ^–½Φ^T, where Λ^–½ =.

Outline of This Chapter

In sections 3.2, 3.3, and 3.4, I discuss three algorithms for the adaptive computation of A^½. Section 3.4 discusses the unique symmetric positive definite solution for A^½. In Sections 3.5, 3.6, and 3.7, I discuss three algorithms for the adaptive computation of A^–½. Section 3.7 describes the unique symmetric positive definite solution for A^–½. Section 3.8 presents experimental results for the six algorithms with 10-dimensional Gaussian data. Section 3.9 concludes the chapter.

Objective Function

Following the methodology described in Section 1.​4, I present the algorithm by first showing an objective function J, whose minimum with respect to matrix W gives us the square root of the asymptotic data correlation matrix A. The objective function is

.     (3.3)

The gradient of J(W) with respect to W is

∇_WJ(W) =  − 4W(A − W^TW).     (3.4)

Adaptive Algorithm

From the gradient in (3.4), we obtain the following adaptive gradient descent algorithm:

,     (3.5)

where η_k is a small decreasing constant and follows assumption A1.2 in the Proofs of Convergence in the GitHub [Chatterjee GitHub].

Objective Function

The objective function J(W), whose minimum with respect to W gives us the square root of A, is

.     (3.6)

The gradient of J(W) with respect to W is

∇_WJ(W) =  − 4(A − WW^T )W.     (3.7)

Adaptive Algorithm

We obtain the following adaptive gradient descent algorithm for square root of A:

,     (3.8)

where η_k is a small decreasing constant.

Adaptive Algorithm

Following the adaptive algorithms (3.5) and (3.8), I now present an algorithm for the computation of a symmetric positive definite square root of A:

,     (3.9)

where η_k is a small decreasing constant and W_k is symmetric.

Objective Function

The objective function J(W), whose minimizer W^* gives us the inverse square root of A, is

.     (3.10)

The gradient of J(W) with respect to W is

∇_WJ(W) =  − 4AW(I − W^TAW).     (3.11)

Adaptive Algorithm

From the gradient in (3.11), we obtain the following adaptive gradient descent algorithm:

     (3.12)

Objective Function

The objective function J(W), whose minimum with respect to W gives us the inverse square root of A, is

.     (3.13)

The gradient of J(W) with respect to W is

∇_WJ(W) =  − 4(I − WAW^T)WA.     (3.14)

Adaptive Algorithm

We obtain the following adaptive algorithm for the inverse square root of A:

,     (3.15)

where η_k is a small decreasing constant.

Adaptive Algorithm

By extending the adaptive algorithms (3.12) and (3.15), I now present an adaptive algorithm for the computation of a symmetric positive definite inverse square root of A:

W_k + 1 = W_k + η_k(I − W_kA_kW_k),     (3.16)

where η_k is a small decreasing constant and W_k is symmetric.

Experiments for Adaptive Square Root Algorithms

I used adaptive algorithms (3.5), (3.8), and (3.9) for Methods 1, 2, and 3, respectively, to compute the square root A, where A is the correlation matrix computed from all collected samples as

I started the algorithms with W₀=I (10X10 identity matrix). At k^th update of each algorithm, I computed the Frobenius norm [Frobenius norm, Wikipedia] of the error between the actual correlation matrix A and the square of W_k that is appropriate for each method. I denote this error by e_k as follows:

,     (3.17)

,     (3.18)

,     (3.19)

.     (3.20)

For each algorithm, I generated A_k from x_k by (2.5) with β=1. In (3.9) I computed the error between the unique positive definite solution of A^½ and its estimate W_k. Figure 3-4 shows the convergence plots for all three methods by plotting the four errors e_k against k. The final values of e_k after 500 samples were e₅₀₀ = 0.451 for Methods 1 and 2, e₅₀₀ = 0.720 for Method 3-1 (3.19), and e₅₀₀ = 0.250 for Method 3-2 (3.20).

It is clear from Figure 3-4 that the errors are all close to zero. The small differences compared to the actual values are due to random fluctuations in the elements of W_k caused by the varying input data.

Experiments for Adaptive Inverse Square Root Algorithms

I used adaptive algorithms (3.12), (3.15), and (3.16) for Methods 1, 2, and 3, respectively, to compute the inverse square root A. I started the algorithms with W₀=I (10X10 identity matrix). At k^th update of each algorithm, I computed the Frobenius norm of the error between the actual correlation matrix A and the inverse square of W_k that is appropriate for each method. I denoted this error by e_k as shown:

,     (3.21)

,     (3.22)

,     (3.23)

,     (3.24)

In (3.24) I computed the error between the unique positive definite solution of A^–½ and its estimate W_k. Figure 3-5 shows the convergence plot for all three methods by plotting the four errors e_k against k. The final values of e_k after 500 samples were e₅₀₀ = 0.419 for Methods 1 and 2, e₅₀₀ = 0.630 for Method 3-1 (3.23), and e₅₀₀ = 0.823 for Method 3-2 (3.24).

It is clear from Figure 3-5 that the errors are all close to zero. As before, experiments with higher epochs show an improvement in the estimation accuracy.