Low rank matrix approximation is an important tool in machine learning. Given a data matrix, low rank approximation helps to find factors, patterns and provides concise representations for the data. Research on low rank approximation usually focus on real matrices. However, in many applications data are binary (categorical) rather than continuous. This leads to the problem of low rank approximation of binary matrix. Here we are given a @math binary matrix @math and a small integer @math . The goal is to find two binary matrices @math and @math of sizes @math and @math respectively, so that the Frobenius norm of @math is minimized. There are two models of this problem, depending on the definition of the dot product of binary vectors: The @math model and the Boolean semiring model. Unlike low rank approximation of real matrix which can be efficiently solved by Singular Value Decomposition, approximation of binary matrix is @math -hard even for @math . In this paper, we consider the problem of Column Subset Selection (CSS), in which one low rank matrix must be formed by @math columns of the data matrix. We characterize the approximation ratio of CSS for binary matrices. For @math model, we show the approximation ratio of CSS is bounded by @math and this bound is asymptotically tight. For Boolean model, it turns out that CSS is no longer sufficient to obtain a bound. We then develop a Generalized CSS (GCSS) procedure in which the columns of one low rank matrix are generated from Boolean formulas operating bitwise on columns of the data matrix. We show the approximation ratio of GCSS is bounded by @math , and the exponential dependency on @math is inherent.
In the @math model, low rank approximation is related to the concept of matrix rigidity introduced by Valiant @cite_22 , as a method of proving lower bounds for linear circuits. For a matrix @math over @math , the rigidity @math is the smallest number of entries of @math that must be changed in order to bring its rank down to @math . Thus for a @math matrix @math , @math is the minimum approximation error possible by a product of a @math matrix @math and a @math matrix @math . By the results of Valiant, an @math matrix @math for which @math , for @math and for some constant @math cannot be computed by a linear circuit of size @math and depth @math . Such rigid matrices exists in abundance -- the challenge is to come up with an explicit construction of a family of rigid matrices. For the low rank approximation problem we are however interested in the setting of @math and we are interested in algorithms rather than explicit matrices.
@cite_22
2031327377 2103972604 2963891483 2014092582
The problem of completing a low-rank matrix from a subset of its entries is often encountered in the analysis of incomplete data sets exhibiting an underlying factor model with applications in collaborative filtering, computer vision, and control. Most recent work has been focused on constructing efficient algorithms for exact or approximate recovery of the missing matrix entries and proving lower bounds for the number of known entries that guarantee a successful recovery with high probability. A related problem from both the mathematical and algorithmic points of view is the distance geometry problem of realizing points in a Euclidean space from a given subset of their pairwise distances. Rigidity theory answers basic questions regarding the uniqueness of the realization satisfying a given partial set of distances. We observe that basic ideas and tools of rigidity theory can be adapted to determine uniqueness of low-rank matrix completion, where inner products play the role that distances play in rigidity theory. This observation leads to efficient randomized algorithms for testing necessary and sufficient conditions for local completion and for testing sufficient conditions for global completion. Crucial to our analysis is a new matrix, which we call the completion matrix, that serves as the analogue of the rigidity matrix. This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understood as the convex relaxation of a rank minimization problem and arises in many important applications as in the task of recovering a large matrix from a small subset of its entries (the famous Netflix problem). Off-the-shelf algorithms such as interior point methods are not directly amenable to large problems of this kind with over a million unknown entries. This paper develops a simple first-order and easy-to-implement algorithm that is extremely efficient at addressing problems in which the optimal solution has low rank. The algorithm is iterative, produces a sequence of matrices @math , and at each step mainly performs a soft-thresholding operation on the singular values of the matrix @math . There are two remarkable features making this attractive for low-rank matrix completion problems. The first is that the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of the iterates @math is empirically nondecreasing. Both these facts allow the algorithm to make use of very minimal storage space and keep the computational cost of each iteration low. On the theoretical side, we provide a convergence analysis showing that the sequence of iterates converges. On the practical side, we provide numerical examples in which @math matrices are recovered in less than a minute on a modest desktop computer. We also demonstrate that our approach is amenable to very large scale problems by recovering matrices of rank about 10 with nearly a billion unknowns from just about 0.4 of their sampled entries. Our methods are connected with the recent literature on linearized Bregman iterations for @math minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms. Low-rank approximation is a common tool used to accelerate kernel methods: the @math kernel matrix @math is approximated via a rank- @math matrix @math which can be stored in much less space and processed more quickly. In this work we study the limits of computationally efficient low-rank kernel approximation. We show that for a broad class of kernels, including the popular Gaussian and polynomial kernels, computing a relative error @math -rank approximation to @math is at least as difficult as multiplying the input data matrix @math by an arbitrary matrix @math . Barring a breakthrough in fast matrix multiplication, when @math is not too large, this requires @math time where @math is the number of non-zeros in @math . This lower bound matches, in many parameter regimes, recent work on subquadratic time algorithms for low-rank approximation of general kernels [MM16,MW17], demonstrating that these algorithms are unlikely to be significantly improved, in particular to @math input sparsity runtimes. At the same time there is hope: we show for the first time that @math time approximation is possible for general radial basis function kernels (e.g., the Gaussian kernel) for the closely related problem of low-rank approximation of the kernelized dataset. This paper concerns the construction of a structured low rank matrix that is nearest to a given matrix. The notion of structured low rank approximation arises in various applications, ranging from signal enhancement to protein folding to computer algebra, where the empirical data collected in a matrix do not maintain either the specified structure or the desirable rank as is expected in the original system. The task to retrieve useful information while maintaining the underlying physical feasibility often necessitates the search for a good structured lower rank approximation of the data matrix. This paper addresses some of the theoretical and numerical issues involved in the problem. Two procedures for constructing the nearest structured low rank matrix are proposed. The procedures are flexible enough that they can be applied to any lower rank, any linear structure, and any matrix norm in the measurement of nearness. The techniques can also be easily implemented by utilizing available optimization packages. The special case of symmetric Toeplitz structure using the Frobenius matrix norm is used to exemplify the ideas throughout the discussion. The concept, rather than the implementation details, is the main emphasis of the paper.