Search

A fundamental technique in machine learning called “embedding” has made significant impact on data representation. Some examples of embedding include word embedding, image embedding and audio embedding. With the embedding techniques, many real-world objects can be represented using matrices. For example, a document can be represented by a matrix, where each row of the matrix represents a word. On the other hand, we have witnessed that many applications continuously generate new data represented by matrices and require real-time query answering on the data. These continuously generated matrices need to be well managed for efficient retrieval. In this paper, we propose a high-performance index for real-time matrix retrieval. Besides fast query response, the index also supports real-time insertion by exploiting the log-structured merge-tree (LSM-tree). Since the index is built for matrices, it consumes much more memory and requires much more time to search than the traditional index for information retrieval. To tackle the challenges, we propose an index with precise and fuzzy inverted lists, and design a series of novel techniques to improve the memory consumption and the search efficiency of the index. The proposed techniques include vector signature, vector residual sorting, hashing based lookup, and dictionary initialization to guarantee the index quality. Comprehensive experimental results show that our proposed index can support real-time search on matrices, and is more time and memory efficient than the state-of-the-art method. [ABSTRACT FROM AUTHOR]

Low rank matrix factorisation is often used in recommender systems as a way of extracting latent features. When dealing with large and sparse datasets, traditional recommendation algorithms face the problem of acquiring large, unrestrained, fluctuating values over predictions. Imposing bounding constraints has been proven an effective solution. However, existing bounding algorithms can only deal with one pair of fixed bounds, and are very time-consuming when applied on large-scale datasets. In this paper, we propose a novel algorithm named Magnitude Bounded Matrix Factorisation (MBMF), which allows different bounds for individual users/items and performs very quickly on large scale datasets. The key idea of our algorithm is to construct a model by constraining the magnitudes of each individual user/item feature vector. By converting coordinate system with radii set as the corresponding magnitudes, MBMF allows the above constrained optimisation problem to become an unconstrained one, which can be solved by unconstrained optimisation algorithms such as the stochastic gradient descent. We also explore an acceleration approach and the choice of magnitudes are given in detail as well. Experiments on synthetic and real datasets demonstrate that in most cases the proposed MBMF is superior over all existing algorithms in terms of accuracy and time complexity. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization (NMF) has been successfully applied in several data mining tasks. Recently, there is an increasing interest in the acceleration of NMF, due to its high cost on large matrices. On the other hand, the privacy issue of NMF over federated data is worthy of attention, since NMF is prevalently applied in image and text analysis which may involve leveraging privacy data (e.g, medical image and record) across several parties (e.g., hospitals). In this paper, we study the acceleration and security problems of distributed NMF. First, we propose a distributed sketched alternating nonnegative least squares(DSANLS) framework for NMF, which utilizes a matrix sketching technique to reduce the size of nonnegative least squares subproblems with a convergence guarantee. For the second problem, we show that DSANLS with modification can be adapted to the security setting, but only for one or limited iterations. Consequently, we propose four efficient distributed NMF methods in both synchronous and asynchronous settings with a security guarantee. We conduct extensive experiments on several real datasets to show the superiority of our proposed methods. The implementation of our methods is available at https://github.com/qianyuqiu79/DSANLS. [ABSTRACT FROM AUTHOR]

The low-rank matrix completion problem is fundamental in both machine learning and computer vision fields with many important applications, such as recommendation system, motion capture, face recognition, and image inpainting. In order to avoid solving the rank minimization problem which is NP-hard, several surrogate functions of the rank have been proposed in the literature. However, the matrix restored from the optimization problem based on the existing surrogate functions seriously deviates from the original one. In this paper, we first design a new non-convex Schatten capped $p$ p norm which generalizes several existing non-convex matrix norms and balances between the rank and the nuclear norm of the matrix. Then, a matrix completion method based on the Schatten capped $p$ p norm is proposed by exploiting the framework of the alternating direction method of multipliers. Meanwhile, the Schatten capped $p$ p norm regularized least squares subproblem is analyzed in detail and is solved explicitly. Finally, we evaluate the performance of the proposed matrix completion method based on extensive experiments in the field of image inpainting. All the experimental results demonstrate that the proposed method can indeed improve the accuracy of matrix completion compared with the existing methods. [ABSTRACT FROM AUTHOR]