Tensor BM‐Decomposition for Compression and Analysis of Video Data

ABSTRACT The Bhattacharya–Messner (BM) product (Messner and Bhattacharya, Journal of Combinatorial Theory, Series A , 55 (2), 1990) provides a means of constructing arbitrary third order tensors from triplets of lateral, frontal, and horizontal slices, the minimum number of such triples being the BM‐rank of the resulting tensor. Thus, if a given tensor can be represented by a small (relative to the dimensions of the tensor) number of triples, the resulting BM‐decomposition (BMD) offers an implicitly compressed representation of the original. In this article, we first show that grayscale surveillance video can be accurately represented by a low BM‐rank decomposition and give methods for efficiently computing this decomposition. We provide theory connecting rank‐revealing matrix factorizations to the BMD and then present a generative model that illustrates that spatio‐temporal video data can be expected to have low BM‐rank. We combine these observations to derive a regularized alternating least squares (ALS) algorithm to compute an approximate BMD of the video tensor. The algorithm is highly parallelizable requiring the solution of many small, independent linear least squares problems. We provide convergence and computational complexity analysis for the proposed algorithms. Extensive numerical results compared against the state‐of‐the‐art matrix based dynamic mode decomposition methods for surveillance video separation show our algorithms can consistently produce results with superior compression properties while simultaneously providing better separation of stationary and nonstationary features in the data. We then introduce a new type of BM‐product suitable for color video and provide an algorithm that shows an impressive ability to extract important temporal information from color video while simultaneously compressing the data.