Fast multiple rank-constrained matrix approximation

Our work addresses methods for a fast multiterm matrix approximation subject to multiple rank constraints. The problem arises in applications associated with data processing systems. For large matrices, finding acceptable matrix approximations may require a quite long time. In practice, this issue may fail associated computation due to a conflict with an available time and computer memory. We provide techniques that allow us to accelerate the associated computation and avoid the above bottleneck. The proposed approach combines a fast pseudoinverse matrix computation, based on the use of a vector tensor product, with a fast low-rank matrix approximation, based on a new extension of a method of bilateral random projections. The provided theoretical and numerical studies demonstrate the faster performance of the proposed method compared to methods based on the SVD computation. It is achieved, in particular, in the cost of ‘a little bit’ worse associated numerical error which, in many practical cases, might be acceptable.