Identifiable Bounded Component Analysis via Minimum Volume Enclosing Parallelotope

In this paper, we revisit bounded component analysis (BCA) and formulate it as a geometric problem of finding the minimum volume enclosing parallelotope (MVEP) of a set of data points in the Euclidean space. A parallelotope is an affine transformation of the standard box, also known as the $L_\infty$-norm ball. An immediate benefit of the novel formulation is that the bounds on the supports of the latent components can be arbitrary, unlike most existing BCA work that assume the bounds are symmetric around zero. The main contribution is that the MVEP solution exactly recovers the latent components, up to the inherent (and inconsequential) permutation, shift, and scaling ambiguities, if the groundtruth components satisfy a so-called ``sufficiently scattered'' condition in the standard box. This is a great improvement to the existing result that requires all vertices of the box are contained in the data set, which requires exponentially many data points, or that of ICA, which essentially requires infinite amount of data points to guarantee exact recovery. We also present a new learning algorithm to solve the (NP-hard) MVEP problem based on Frank-Wolfe, and show numerically that the performance is surprisingly effective.