Cong Tran, Won-Yong Shin · 2021
Due to practical reasons such as limited resources and privacy settings specified by users on social media, most network data tend to be only partially observed with both missing nodes and missing edges. Thus, it is of paramount importance to infer the missing parts of the networks since incomplete network data may severely degrade the performance of downstream analyses. In this paper, we provide a comprehensive survey on network completion, which is a more challenging task than the well-studied low-rank matrix completion problem in the sense that a row and a column of an adjacency matrix shall be entirely unobservable when a node is completely missing from the given network. Specifically, we first define the problem of network completion. Then, we review two state-of-the-art algorithms for discovering the missing part of an underlying network, namely KronEM and DeepNC. We also show a performance comparison between the two algorithms via experimental evaluation. Finally, we discuss the potentials and limitations of the two algorithms.
Cited by 1
Morris Newman · Proceedings of the American Mathematical Society · 1985
Let $R$ be a principal ideal ring, ${M_{t,n}}$ the set of $t \times n$ matrices over $R$. The following results are proved: (a) Let $D \in {M_{n,n}}$. Then the least nonnegative integer $t$ such that a matrix $\left [ {\begin {array}{*{20}{c}} * & * \\ * & D \\ \end {array} } \right ]$ exists which belongs to ${\text {GL(}}n + t,R)$ is $t = n - p$, where $p$ is the number of invariant factors of $D$ equal to 1. (b) Any primitive element of ${M_{1,2n}}$ may be completed to a $2n \times 2n$ symplectic matrix. (c) If $A,B \in {M_{n,n}}$ are such that $[A,B]$ is primitive and $A{B^T}$ is symmetric, then $[A,B]$ may be completed to a $2n \times 2n$ symplectic matrix. (d) If $A \in {M_{t,t}},B \in {M_{t,n - t}}$, are such that $[A,B]$ is primitive and $A$ is symmetric, then $[A,B]$ may be completed to a symmetric element of ${\text {SL(}}n,R{\text {)}}$, provided that $1 \leqslant t \leqslant n/3$. (e) If $n \geqslant 3$, then any primitive element of ${M_{1,n}}$ occurs as the first row of the commutator of two elements of ${\text {SL(}}n,R{\text {)}}$.
Cited by 5
Morris Newman · Proceedings of the American Mathematical Society · 1985
Let Rbea principal ideal ring, M, " the set of / X n matrices over R. The following results are proved :(a) Let D e M" ".Then the least nonnegative integer t such that a matrix [% p] exists which belongs to GL(n + t, R) is t = n -p, where p is the number of invariant factors of D equal to 1.(b) Any primitive element of M 2" may be completed to a 2n X 2n symplectic matrix.(c) If A, B s M" " are such that [A, B] is primitive and AB is symmetric, then [A, B] may be completed to a 2 X In symplectic matrix.(d) If A e M, ,, B e M, "_, are such that [A, B] is primitive and A is symmetric, then [A, B] may be completed to a symmetric element of SL(, R), provided that 1 t h/3.(e) If n > 3, then any primitive element of Mln occurs as the first row of the commutator of two elements of SL(n, R).Basic Result.Let a be a primitive element of Mx n.Then an element ofGL(n, R) exists whose first row is a.If n ^ 2, an element ofSL(n, R) exists whose first row is a.
Cited by 8Open access
Mokhtar Z. Alaya, Olga Klopp · arXiv (Cornell University) · 2018
Matrix completion aims to reconstruct a data matrix based on observations of\na small number of its entries. Usually in matrix completion a single matrix is\nconsidered, which can be, for example, a rating matrix in recommendation\nsystem. However, in practical situations, data is often obtained from multiple\nsources which results in a collection of matrices rather than a single one. In\nthis work, we consider the problem of collective matrix completion with\nmultiple and heterogeneous matrices, which can be count, binary, continuous,\netc. We first investigate the setting where, for each source, the matrix\nentries are sampled from an exponential family distribution. Then, we relax the\nassumption of exponential family distribution for the noise and we investigate\nthe distribution-free case. In this setting, we do not assume any specific\nmodel for the observations. The estimation procedures are based on minimizing\nthe sum of a goodness-of-fit term and the nuclear norm penalization of the\nwhole collective matrix. We prove that the proposed estimators achieve fast\nrates of convergence under the two considered settings and we corroborate our\nresults with numerical experiments.\n
Cited by 2Open access
Elad Hazan, Adam Tauman Kalai, Varun Kanade et al. · 2023
Cited by 0
Rina Foygel Barber, Yu Gui, Cong Ma · 2023
Cited by 1
Yunzhen Yao, Liangzu Peng, Manolis C. Tsakiris · 2021
Inspired by real phase retrieval and low-rank matrix recovery, we introduce the problem of unsigned matrix retrieval, where the aim is to recover a matrix of bounded-rank from a sign-ambiguous version of it. Allowing for missing entries in addition to sign ambiguities leads to the problem of unsigned matrix completion. Under an algebraic geometry framework, we provide fundamental results regarding unique recovery up to a class of rank-preserving sign patterns and finite completability.
Cited by 0
Glória Cravo · Linear Algebra and its Applications · 2009
Cited by 22
Abdo Y. Alfakih, Henry Wolkowicz · International series in management science/operations research/International series in operations research & management science · 2000
Cited by 28
Xuan Li, Li Zhang · 2022
Collaborative filtering (CF) is typically a matrix completion (MC) problem where the unknown values of the rating matrix are predicted by finding similar rating patterns based on the given entries. The most common paradigm of MC is to factorize the rating matrix into two low-rank matrices. The basic matrix factorization (MF) and its extensions, i.e. conventional MF-based models, have achieved great success in the past and recently models based on deep learning have become popular. However, some recent works have pointed out that many newly proposed methods are outperformed by conventional MF-based models, which demonstrates the simplicity but effectiveness of the basic MF and its extensions. Finding the basic MF cannot be formulated by Probabilistic Matrix Factorization (PMF), this paper proposes a new model called Probabilistic Matrix Completion (PMC), which can interpret the basic MF from a probabilistic perspective. Unlike PMF, which samples each latent vector for each row in the rating matrix indiscriminately, PMC considers different sample frequency between rows (and columns) and computes the prior distribution based on the observed entries. To further demonstrate the difference between PMF and PMC, we incorporate geometric structure into PMC and finally get a model named GPMC that can outperform various state-of-the-art CF methods in terms of rating prediction. We validate our claims on six real-world datasets.
Cited by 0
Makoto Yamashita, Kazuhide Nakata, Makoto Yamashita et al. · 2013
Cited by 0
Hazan, E, Kalai, AT, Kanade, V et al. · Oxford University Research Archive (ORA) (University of Oxford) · 2024
The matrix completion problem involves reconstructing a low-rank matrix by using a given set of revealed (and potentially noisy) entries. Although existing methods address the completion of the entire matrix, the accuracy of the completed entries can vary significantly across the matrix, due to differences in the sampling distribution. For instance, users may rate movies primarily from their country or favorite genres, leading to inaccurate predictions for the majority of completed entries.We propose a novel formulation of the problem as Partial Matrix Completion, where the objective is to complete a substantial subset of the entries with high confidence. Our algorithm efficiently handles the unknown and arbitrarily complex nature of the sampling distribution, ensuring high accuracy for all completed entries and sufficient coverage across the matrix. Additionally, we introduce an online version of the problem and present a low-regret efficient algorithm based on iterative gradient updates. Finally, we conduct a preliminary empirical evaluation of our methods.
Cited by 0
Zechu Steven Li, Xiao-Yang Liu, Xiaodong Wang · 2022
Cited by 0
Yang Cao, Yao Xie · 2015
We extend the theory of matrix completion to the case where we make Poisson observations for a subset of entries of a low-rank matrix. We consider the (now) usual matrix recovery formulation through maximum likelihood with proper constraints on the matrix M of size d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -by-d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> , and establish theoretical upper and lower bounds on the recovery error. Our bounds are nearly optimal up to a factor on the order of O(log(d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> )). These bounds are obtained by adapting the arguments used for one-bit matrix completion [1] (although these two problems are different in nature) and the adaptation requires new techniques exploiting properties of the Poisson likelihood function and tackling the difficulties posed by the locally sub-Gaussian characteristic of the Poisson distribution. Our results highlight a few important distinctions of Poisson matrix completion compared to the prior work in matrix completion including having to impose a minimum signal-to-noise requirement on each observed entry. We also develop an efficient iterative algorithm and demonstrate its good performance in recovering solar flare images.
Cited by 8
SpringerReference · 2012
Cited by 0
Tomno · SU+ Digital Repository (Strathmore University) · 2017
Paper presented at the 4th Strathmore International Mathematics Conference (SIMC 2017), 19 - 23 June 2017, Strathmore University, Nairobi, Kenya.
Cited by 0Open access
Shayok Chakraborty, Jiayu Zhou, Vineeth N Balasubramanian et al. · 2013
Recovering a matrix from a sampling of its entries is a problem of rapidly growing interest and has been studied under the name of matrix completion. It occurs in many areas of engineering and applied science. In most machine learning and data mining applications, it is possible to leverage the expertise of human oracles to improve the performance of the system. It is therefore natural to extend this idea of "human-in-the-loop" to the matrix completion problem. However, considering the enormity of data in the modern era, manually completing all the entries in a matrix will be an expensive process in terms of time, labor and human expertise, human oracles can only provide selective supervision to guide the solution process. Thus, appropriately identifying a subset of missing entries (for manual annotation) in an incomplete matrix is of paramount practical importance, this can potentially lead to better reconstructions of the incomplete matrix with minimal human effort. In this paper, we propose novel algorithms to address this issue. Since the query locations are actively selected by the algorithms, we refer to these methods as active matrix completion algorithms. The proposed techniques are generic and the same frameworks can be used in a wide variety of applications including recommendation systems, transductive / multi-label active learning, active learning in regression and active feature acquisition among others. Our extensive empirical analysis on several challenging real-world datasets certify the merit and versatility of the proposed frameworks in efficiently exploiting human intelligence in data mining / machine learning applications.
Cited by 50
Mokhtar Z. Alaya, Olga Klopp · arXiv (Cornell University) · 2018
Matrix completion aims to reconstruct a data matrix based on observations of a small number of its entries. Usually in matrix completion a single matrix is considered, which can be, for example, a rating matrix in recommendation system. However, in practical situations, data is often obtained from multiple sources which results in a collection of matrices rather than a single one. In this work, we consider the problem of collective matrix completion with multiple and heterogeneous matrices, which can be count, binary, continuous, etc. We first investigate the setting where, for each source, the matrix entries are sampled from an exponential family distribution. Then, we relax the assumption of exponential family distribution for the noise and we investigate the distribution-free case. In this setting, we do not assume any specific model for the observations. The estimation procedures are based on minimizing the sum of a goodness-of-fit term and the nuclear norm penalization of the whole collective matrix. We prove that the proposed estimators achieve fast rates of convergence under the two considered settings and we corroborate our results with numerical experiments.
Cited by 8Open access
Leslie Hogben, Amy Wangsness · 2006
A partial matrix is a rectangular array of numbers in which some entries are specified while others are free to be chosen. A completion of a partial matrix is a specific choice of values for the unspecified entries. A matrix completion problem asks whether a partial matrix (or family of partial matrices with a given pattern of specified entries) has a completion of a specific type, such as a positive definite matrix. In some cases, a “best” completion is sought.
Cited by 7
Jicong Fan, Jieyu Cheng · Neural Networks · 2017
Cited by 187