2.1 Introduction

In this chapter, I present algorithms for the adaptive solutions of matrix algebra problems from a sequence of matrices. The streams or sequences can be random matrices {A_k} or {B_k}, or the correlation matrices of random vector sequences {x_k} or {y_k}. Examples of matrix algebra are matrix inversion, square root, inverse square root, eigenvectors, generalized eigenvectors, singular vectors, and generalized singular vectors.

This chapter additionally covers the basic terminologies and methods used throughout the remaining chapters. I also present well-known adaptive algorithms to compute the mean, median, covariance, inverse covariance, and correlation matrices from random matrix or vector sequences. Furthermore, I present a new algorithm to compute the normalized mean of a random vector sequence.

For the sake of simplicity, let’s assume that the multidimensional data {x_k∈ℜⁿ} arrives as a sequence. From this data sequence, we can derive a matrix sequence {}. We define the data correlation matrix A as follows:

.     (2.1)

2.2 Stationary and Non-Stationary Sequences

In practical implementations, we face two types of sequences: stationary and non-stationary . A sequence {x_k} is considered asymptotically (weak) stationary if is a constant. For a non-stationary sequence {x_k}, remains a function of both k and m, and is a function of k. Examples of non-stationary data are given in Publicly Real-World Datasets to Evaluate Stream Learning Algorithms [Vinicius Souza et al. 20]. Figure 2-1 shows examples of stationary and non-stationary data.

Non-stationarity in data can be detected by well-known techniques described in this reference [Shay Palachy 19].

2.3 Use Cases for Adaptive Mean, Median, and Covariances

Adaptive mean computation is important in real-world applications even though it is one of the simplest algorithms.

Handwritten Character Recognition

Consider the problem of detecting handwritten number 8. Figure 2-2 shows six instances of the number 8 from the Keras dataset MNIST images [Keras, MNIST].

One algorithm to recognize the number 8 with all its variations is to find the mean set of pixels that represent it. Due to random variations in handwriting, it is difficult to compile all variations of each character ahead of time. It is important to design an adaptive learning scheme whereby instantaneous variations in these characters are immediately represented in the machine learning algorithm.

The adaptive mean detection algorithm is helpful in finding the common pattens that represent the number 8. Figure 2-3 shows a template for the number 8 obtained by the adaptive mean algorithm given in Eq. (2.2).

Anomaly Detection of Streaming Data

A simple yet powerful algorithm to detect anomalies in data is to calculate the median and compare the current value against the median of the data. Figure 2-4 shows streaming data [Yahoo Research Webscope S5 Data] containing occasional anomalous values. We adaptively computed the median with algorithm (2.20) and compared it against the data to detect anomalies. Here the data samples are in blue, the adaptive median is in green, and anomalies are in red.

More on this topic is discussed in Chapter 8.

2.4 Adaptive Mean and Covariance of Nonstationary Sequences

In the stationary case, given a sequence {x_k∈ℜⁿ}, we can compute the adaptive mean m_k as follows:

.     (2.2)

Similarly, the adaptive correlation A_k is

.     (2.3)

Here we use all samples up to time instant k.

If, however, the data is non-stationary, we use a forgetting factor 0<β≤1 to implement an effective window of size 1/(1–β) as

     (2.4)

and

.     (2.5)

This effective window ensures that the past data samples are downweighted with an exponentially fading window compared to the recent ones in order to afford the tracking capability of the adaptive algorithm. The exact value of β depends on the specific application. Generally speaking, for slow time-varying {x_k}, β is chosen close to 1 to implement a large effective window, whereas for fast time-varying {x_k}, β is chosen near zero for a small effective window [Benveniste et al. 90].

2.5 Adaptive Covariance and Inverses

Given the mean and correlations discussed before, the adaptive covariance matrix B_k can also be computed as follows:

     (2.6)

From the adaptive correlation matrix A_k in (2.5), the inverse correlation matrix can be obtained adaptively by the Sherman-Morrison formula [Sherman–Morrison, Wikipedia] as

.     (2.7)

Similarly, the inverse covariance matrix can be obtained adaptively as

.     (2.8)

2.6 Adaptive Normalized Mean Algorithm

The most obvious choice for an adaptive normalized mean algorithm is to use (2.2) and normalize each m_k. However, a more efficient algorithm can be obtained from the following cost function whose minimizer w^* is the asymptotic normalized mean m/‖m‖, where m = lim_k → ∞E[x_k]:

,     (2.9)

where α is a Lagrange multiplier that enforces the constraint that the mean is normalized. The gradient of J(w_k;x_k) with respect to w_k is

.     (2.10)

Multiplying (2.10) by and applying the constraint , we obtain

.     (2.11)

Using this α in (2.11), we obtain the adaptive gradient descent algorithm for normalized mean:

,     (2.12)

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

2.7 Adaptive Median Algorithm

Given a sequence {x_k}, its asymptotic median μ satisfies the following:

     (2.17)

where P(E) is the probability measure of event E and 0 ≤ P(E) ≤ 1. The objective function J(w_k;x_k) whose minimizer w^* is the asymptotic median μ is

J(w_k; x_k) = ‖x_k − w_k‖.     (2.18)

The gradient of J(w_k;x_k) with respect to w_k is

,     (2.19)

where sgn(.) is the sign operator (sgn(x)=1 if x≥0 and –1 if x<0). From the gradient in (2.19), we obtain the adaptive gradient descent algorithm:

w_k + 1 = w_k + η_k sgn (x_k − w_k).     (2.20)

2.8 Experimental Results

The purpose of these experiments is to demonstrate the performance and accuracies of the adaptive algorithms for mean, correlation, inverse correlation, inverse covariance, normalized mean, and median.

I generated 1,000 sample vectors {x_k} of five-dimensional Gaussian data (i.e., n=5) with the following mean and covariance:

Mean = [10 7 6 5 1],

Covariance = .

For each algorithm, I computed the error as the Frobenius norm [Frobenius norm, Wikipedia] of the estimated value at each iteration of the algorithm and the actual computed value from all of the 1,000 samples.

I computed the mean vector and correlation matrices by the adaptive algorithms (2.4) and (2.5), respectively. Figure 2-5 shows the results.

I computed the inverses of the correlation and covariance matrices with algorithms (2.7) and (2.8), respectively. Figure 2-6 shows the results.

I computed the normalized mean by adaptive algorithms (2.12) and (2.14), and the median by algorithm (2.20). For each value of k in these algorithms, I computed the errors between the w_k (estimate) and the actual values of normalized mean and median obtained from the entire 1,000 sample data. I used the 5X1 zero vector as the starting values (w₀) for all algorithms. The results are shown in Figure 2-7.

All adaptive algorithms converged rapidly. After the 1,000 samples were processed, the errors were 0.0043 for algorithms (2.14) and (2.16), and 0.0408 for algorithm (2.20). See the code in the GitHub repository [Chatterjee GitHub].