A distribution-free method for change point detection in non-sparse high dimensional data

Figures & data

Table 1 Frequency and average number of the detected change points over 250 replications by each of the methods when there is one true change point, also including the case with no change point.

${\mathit{\mu }}_2$	n	p	Number of true change points	Method	Frequency of the detected change points	Average number of detected change points
					0	1
	45	500	0	Permutation	0.98	0.02	0.02
	45	500	0	Asymptotic	0.98	0.02	0.02
${\mathbf{0}}_p$	45	500	0	E-divisive	0.97	0.03	0.03
	45	500	0	Inspect	0.97	0.03	0.03
	45	500	0	HDcpdetect	0.98	0.02	0.02
	45	1000	0	Permutation	0.97	0.03	0.03
	45	1000	0	Asymptotic	0.96	0.04	0.04
${\mathbf{0}}_p$	45	1000	0	E-divisive	0.95	0.05	0.05
	45	1000	0	Inspect	0.94	0.06	0.06
	45	1000	0	HDcpdetect	0.96	0.04	0.04
	45	1500	0	Permutation	0.95	0.05	0.05
	45	1500	0	Asymptotic	0.95	0.05	0.05
${\mathbf{0}}_p$	45	1500	0	E-divisive	0.96	0.04	0.04
	45	1500	0	Inspect	0.94	0.06	0.06
	45	1500	0	HDcpdetect	0.96	0.04	0.04
	45	500	1	Permutation	0.80	0.20	0.20
	45	500	1	Asymptotic	0.73	0.27	0.27
$(0.1\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	45	500	1	E-divisive	0.83	0.17	0.17
	45	500	1	Inspect	0.91	0.09	0.09
	45	500	1	HDcpdetect	0.87	0.13	0.13
	45	1000	1	Permutation	0.42	0.58	0.58
	45	1000	1	Asymptotic	0.33	0.67	0.67
$(0.1\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	45	1000	1	E-divisive	0.67	0.33	0.33
	45	1000	1	Inspect	0.93	0.07	0.07
	45	1000	1	HDcpdetect	0.71	0.29	0.29
	45	1500	1	Permutation	0.16	0.84	0.84
	45	1500	1	Asymptotic	0.13	0.87	0.87
$(0.1\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	45	1500	1	E-divisive	0.38	0.62	0.62
	45	1500	1	Inspect	0.93	0.07	0.07
	45	1500	1	HDcpdetect	0.49	0.51	0.51
	45	500	1	Permutation	0.12	0.88	0.88
	45	500	1	Asymptotic	0.10	0.90	0.90
$(0.2\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	45	500	1	E-divisive	0.14	0.86	0.86
	45	500	1	Inspect	0.77	0.23	0.23
	45	500	1	HDcpdetect	0.15	0.85	0.85
	45	1000	1	Permutation	0.00	1.00	1.00
	45	1000	1	Asymptotic	0.00	1.00	1.00
$(0.2\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	45	1000	1	E-divisive	0.03	0.97	0.97
	45	1000	1	Inspect	0.72	0.28	0.28
	45	1000	1	HDcpdetect	0.05	0.95	0.95
	45	1500	1	Permutation	0.00	1.00	1.00
	45	1500	1	Asymptotic	0.00	1.00	1.00
$(0.2\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	45	1500	1	E-divisive	0.02	0.98	0.98
	45	1500	1	Inspect	0.63	0.37	0.37
	45	1500	1	HDcpdetect	0.02	0.98	0.98

Table 2 Frequency and average number of the correctly detected change points over 250 replications by each of the methods when there are three true change points, also including the case with no change points.

${\mathit{\mu }}_2$	n	p	Number of true change points	Method	Frequency of the detected change points	Average number of detected change points
					0	1	2	3
	90	500	0	Permutation	0.97	0.03	0.00	0.00	0.03
	90	500	0	Asymptotic	0.97	0.03	0.00	0.00	0.03
${\mathbf{0}}_p$	90	500	0	E-divisive	0.96	0.04	0.00	0.00	0.04
	90	500	0	Inspect	0.95	0.05	0.00	0.00	0.05
	90	500	0	HDcpdetect	0.96	0.04	0.00	0.00	0.04
	90	1000	0	Permutation	0.97	0.03	0.00	0.00	0.03
	90	1000	0	Asymptotic	0.96	0.04	0.00	0.00	0.04
${\mathbf{0}}_p$	90	1000	0	E-divisive	0.95	0.05	0.00	0.00	0.05
	90	1000	0	Inspect	0.96	0.04	0.00	0.00	0.04
	90	1000	0	HDcpdetect	0.95	0.05	0.00	0.00	0.05
	90	1500	0	Permutation	0.96	0.04	0.00	0.00	0.04
	90	1500	0	Asymptotic	0.96	0.04	0.00	0.00	0.04
${\mathbf{0}}_p$	90	1500	0	E-divisive	0.96	0.04	0.00	0.00	0.04
	90	1500	0	Inspect	0.94	0.06	0.00	0.00	0.06
	90	1500	0	HDcpdetect	0.94	0.06	0.00	0.00	0.06
	90	500	3	Permutation	0.32	0.46	0.20	0.02	0.92
	90	500	3	Asymptotic	0.24	0.48	0.26	0.02	1.06
$(0.1\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	90	500	3	E-divisive	0.30	0.56	0.12	0.02	0.86
	90	500	3	Inspect	0.56	0.38	0.06	0.00	0.50
	90	500	3	HDcpdetect	0.32	0.62	0.06	0.00	0.74
	90	1000	3	Permutation	0.09	0.24	0.56	0.11	1.69
	90	1000	3	Asymptotic	0.06	0.27	0.50	0.17	1.77
$(0.1\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	90	1000	3	E-divisive	0.07	0.60	0.23	0.10	1.36
	90	1000	3	Inspect	0.46	0.45	0.09	0.00	0.63
	90	1000	3	HDcpdetect	0.20	0.63	0.14	0.03	1.00
	90	1500	3	Permutation	0.00	0.05	0.19	0.76	2.71
	90	1500	3	Asymptotic	0.00	0.05	0.15	0.80	2.75
$(0.1\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	90	1500	3	E-divisive	0.05	0.25	0.46	0.24	1.89
	90	1500	3	Inspect	0.22	0.58	0.19	0.01	0.99
	90	1500	3	HDcpdetect	0.08	0.44	0.38	0.10	1.50
	90	500	3	Permutation	0.00	0.02	0.18	0.80	2.78
	90	500	3	Asymptotic	0.00	0.02	0.16	0.82	2.80
$(0.2\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	90	500	3	E-divisive	0.00	0.02	0.24	0.74	2.72
	90	500	3	Inspect	0.06	0.30	0.36	0.28	1.86
	90	500	3	HDcpdetect	0.01	0.45	0.14	0.40	1.93
	90	1000	3	Permutation	0.00	0.00	0.00	1.00	3.00
	90	1000	3	Asymptotic	0.00	0.00	0.00	1.00	3.00
$(0.2\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	90	1000	3	E-divisive	0.00	0.00	0.14	0.86	2.86
	90	1000	3	Inspect	0.00	0.13	0.57	0.30	2.16
	90	1000	3	HDcpdetect	0.00	0.53	0.19	0.28	1.75
	90	1500	3	Permutation	0.00	0.00	0.00	1.00	3.00
	90	1500	3	Asymptotic	0.00	0.00	0.00	1.00	3.00
$(0.2\times {\mathbf{1}}_{3p/4},0\times {\mathbf{1}}_{p/4})$	90	1500	3	E-divisive	0.00	0.00	0.02	0.98	2.98
	90	1500	3	Inspect	0.00	0.08	0.35	0.57	2.49
	90	1500	3	HDcpdetect	0.00	0.85	0.04	0.11	1.26

Table 3 Frequency and average number of the detected change points over 250 replications by each of the methods when there is a true change in variance of observations.

$({\mathit{\mu }}_1,{\mathbf{\Sigma }}_1)$	$({\mathit{\mu }}_2,{\mathbf{\Sigma }}_2)$	n	p	Method	Frequency of the detected change points	Average number of detected change points
					0	1
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	500	Permutation	0.87	0.13	0.13
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	500	Asymptotic	0.85	0.15	0.15
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	500	E-divisive	0.98	0.02	0.02
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	500	Inspect	0.98	0.02	0.02
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	500	HDcpdetect	0.99	0.01	0.01
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1000	Permutation	0.32	0.68	0.68
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1000	Asymptotic	0.29	0.71	0.71
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1000	E-divisive	0.96	0.04	0.04
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1000	Inspect	0.96	0.04	0.04
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1000	HDcpdetect	0.98	0.02	0.02
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1500	Permutation	0.09	0.91	0.91
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1500	Asymptotic	0.08	0.92	0.92
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1500	E-divisive	0.96	0.04	0.04
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1500	Inspect	0.97	0.03	0.03
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.6{\mathit{V}}_p)$	45	1500	HDcpdetect	0.97	0.03	0.03
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	500	Permutation	0.09	0.91	0.91
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	500	Asymptotic	0.09	0.91	0.91
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	500	E-divisive	0.86	0.14	0.14
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	500	Inspect	0.97	0.03	0.03
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	500	HDcpdetect	0.98	0.02	0.02
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1000	Permutation	0.00	1.00	1.00
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1000	Asymptotic	0.00	1.00	1.00
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1000	E-divisive	0.72	0.28	0.28
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1000	Inspect	0.94	0.06	0.06
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1000	HDcpdetect	0.97	0.03	0.03
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1500	Permutation	0.00	1.00	1.00
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1500	Asymptotic	0.00	1.00	1.00
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1500	E-divisive	0.49	0.51	0.51
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1500	Inspect	0.95	0.05	0.05
$({\mathbf{0}}_p,0.5{\mathit{V}}_p)$	$({\mathbf{0}}_p,0.7{\mathit{V}}_p)$	45	1500	HDcpdetect	0.96	0.04	0.04

Table 4 Frequency and average number of the detected change points over 250 replications by each of the methods when there is a change in distribution of observations while their mean and variance remain the same.

Two different distributions	n	p	Number of true change points	Method	Frequency of the detected change points	Average number of detected change points
					0	1
	45	500	1	Univariate	0.86	0.14	0.14
	45	500	1	L2 norm	0.84	0.16	0.16
	45	500	1	L1 norm	0.74	0.26	0.26
$N(0,5/3)$ & t(5)	45	500	1	E-divisive	0.55	0.45	0.45
	45	500	1	Inspect	0.99	0.01	0.01
	45	500	1	HDcpdetect	0.98	0.02	0.02
	45	1000	1	Univariate	0.83	0.17	0.17
	45	1000	1	L 2 norm	0.80	0.20	0.20
	45	1000	1	L 1 norm	0.69	0.31	0.31
$N(0,5/3)$ & t(5)	45	1000	1	E-divisive	0.51	0.49	0.49
	45	1000	1	Inspect	0.97	0.03	0.03
	45	1000	1	HDcpdetect	0.96	0.04	0.04
	45	1500	1	Univariate	0.80	0.20	0.20
	45	1500	1	L 2 norm	0.77	0.23	0.23
	45	1500	1	L 1 norm	0.66	0.34	0.34
$N(0,5/3)$ & t(5)	45	1500	1	E-divisive	0.50	0.50	0.50
	45	1500	1	Inspect	0.94	0.06	0.06
	45	1500	1	HDcpdetect	0.94	0.06	0.06
	45	500	1	Univariate	0.99	0.01	0.01
	45	500	1	L2 norm	0.98	0.02	0.02
	45	500	1	L1 norm	0.58	0.42	0.42
N(1, 1) & $\hspace{0.17em}\mathrm{Exp}\hspace{0.17em}(1)$	45	500	1	E-divisive	0.99	0.01	0.01
	45	500	1	Inspect	0.96	0.04	0.04
	45	500	1	HDcpdetect	0.99	0.01	0.01
	45	1000	1	Univariate	0.98	0.02	0.02
	45	1000	1	L2 norm	0.95	0.05	0.05
	45	1000	1	L1 norm	0.29	0.71	0.71
N(1, 1) & $\hspace{0.17em}\mathrm{Exp}\hspace{0.17em}(1)$	45	1000	1	E-divisive	0.98	0.02	0.02
	45	1000	1	Inspect	0.94	0.06	0.06
	45	1000	1	HDcpdetect	0.98	0.02	0.02
	45	1500	1	Univariate	0.96	0.04	0.04
	45	1500	1	L2 norm	0.90	0.10	0.10
	45	1500	1	L1 norm	0.09	0.91	0.91
N(1, 1) & $\hspace{0.17em}\mathrm{Exp}\hspace{0.17em}(1)$	45	1500	1	E-divisive	0.92	0.08	0.08
	45	1500	1	Inspect	0.93	0.07	0.07
	45	1500	1	HDcpdetect	0.97	0.03	0.03

Figure 1 Illustrative example with one change point: plots for all elements of the distance matrix D obtained using the dissimilarity measure $d({\mathit{X}}_i,{\mathit{X}}_j)$ in (3) with both the univariate and multivariate distance functions, as well as for all column sums of the difference distance matrix Δ.

Figure 2 The sets ${\nabla }_{\widehat{\tau }}^{-}$ and ${\nabla }_{\widehat{\tau }}^{+}$ with the estimated change point location $\widehat{\tau }$.

Figure 3 Illustrative example with two change points: plots for all elements of the distance matrix D obtained using the dissimilarity measure $d({\mathit{X}}_i,{\mathit{X}}_j)$ in (3) with both the univariate and multivariate distance functions, as well as for all column sums of the difference distance matrix Δ.

Figure 4 The estimate of change point from each of the methods over 250 replications with a true single change point at location $3n/5+1=28$ when n = 45.

Figure 5 Average number of the total change points detected (correct or incorrect detection) over 250 replications by each of the methods for multiple change point detection.

Figure 6 Change point plots for the S&P 500 data over the time period 1/1/2020 and 30/6/2020 during the COVID-19 pandemic. In plot (b) the two trading days 13th and 16th March 2020 show the largest total dissimilarity from all the other days and are marked by vertical bars (in green).