{"title":"Matrix Completion with Heterogeneous Observation Cost Using Sparsity-Number of Column-Space","authors":"Ilqar Ramazanli","volume":186,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":32,"pagesEnd":38,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10012575","abstract":"<p>The matrix completion problem has been studied broadly under many underlying conditions. In many real-life scenarios, we could expect elements from distinct columns or distinct positions to have a different cost. In this paper, we explore this generalization under adaptive conditions. We approach the problem under two different cost models. The first one is that entries from different columns have different observation costs, but, within the same column, each entry has a uniform cost. The second one is any two entry has different observation cost, despite being the same or different columns. We provide complexity analysis of our algorithms and provide tightness guarantees.<\/p>","references":"[1] Candes, Emmanuel J., and Yaniv Plan. Matrix completion with noise.\r\nProceedings of the IEEE 98.6 (2010): 925-936.\r\n[2] Balcan, Maria-Florina F., and Hongyang Zhang. Noise-tolerant life-long\r\nmatrix completion via adaptive sampling. Advances in Neural Information\r\nProcessing Systems 29 (2016).\r\n[3] B\u00b4ecigneul, Gary, and Octavian-Eugen Ganea. Riemannian adaptive\r\noptimization methods. arXiv preprint arXiv:1810.00760 (2018).\r\n[4] Bertsimas, Dimitris, and Michael Lingzhi Li. Fast exact matrix\r\ncompletion: A unified optimization framework for matrix completion.\r\nJournal of Machine Learning Research 21.231 (2020): 1-43.\r\n[5] Bhargava, Aniruddha, Ravi Ganti, and Rob Nowak. Active positive\r\nsemidefinite matrix completion: Algorithms, theory and applications.\r\nArtificial Intelligence and Statistics. PMLR, 2017.\r\n[6] Cai, Jian-Feng, Emmanuel J. Cand`es, and Zuowei Shen. A singular\r\nvalue thresholding algorithm for matrix completion. SIAM Journal on\r\noptimization 20.4 (2010): 1956-1982.\r\n[7] Cand`es, Emmanuel J., and Benjamin Recht. Exact matrix completion\r\nvia convex optimization. Foundations of Computational mathematics 9.6\r\n(2009): 717-772. [8] Cand`es, Emmanuel J., and Terence Tao. The power of convex relaxation:\r\nNear-optimal matrix completion. IEEE Transactions on Information\r\nTheory 56.5 (2010): 2053-2080.\r\n[9] Candes, Emmanuel J., and Benjamin Recht. Exact low-rank matrix\r\ncompletion via convex optimization. 2008 46th Annual Allerton\r\nConference on Communication, Control, and Computing. IEEE, 2008.\r\n[10] Chistov, Alexander L., and D. Yu Grigor\u2019Ev. Complexity of quantifier\r\nelimination in the theory of algebraically closed fields. International\r\nSymposium on Mathematical Foundations of Computer Science. Springer,\r\nBerlin, Heidelberg, 1984.\r\n[11] Deshpande, Amit, et al. Matrix approximation and projective clustering\r\nvia volume sampling. Theory of Computing 2.1 (2006): 225-247.\r\n[12] Frieze, Alan, Ravi Kannan, and Santosh Vempala. Fast Monte-Carlo\r\nalgorithms for finding low-rank approximations. Journal of the ACM\r\n(JACM) 51.6 (2004): 1025-1041.\r\n[13] Gross, David. Recovering low-rank matrices from few coefficients in any\r\nbasis. IEEE Transactions on Information Theory 57.3 (2011): 1548-1566.\r\n[14] Helman, Paul, Bernard ME Moret, and Henry D. Shapiro. An\r\nexact characterization of greedy structures. SIAM Journal on Discrete\r\nMathematics 6.2 (1993): 274-283.\r\n[15] Huang, Yuge, et al. Curricularface: adaptive curriculum learning loss\r\nfor deep face recognition. proceedings of the IEEE\/CVF conference on\r\ncomputer vision and pattern recognition. 2020.\r\n[16] Jain, Prateek, and Praneeth Netrapalli. Fast exact matrix completion with\r\nfinite samples. Conference on Learning Theory. PMLR, 2015.\r\n[17] Keshavan, Raghunandan, Andrea Montanari, and Sewoong Oh. Matrix\r\ncompletion from noisy entries. Advances in neural information processing\r\nsystems 22 (2009).\r\n[18] Kong, Yajing, et al. Adaptive Curriculum Learning. Proceedings of the\r\nIEEE\/CVF International Conference on Computer Vision. 2021.\r\n[19] Krishnamurthy, Akshay, and Aarti Singh. Low-rank matrix and tensor\r\ncompletion via adaptive sampling. Advances in neural information\r\nprocessing systems 26 (2013).\r\n[20] Krishnamurthy, Akshay, and Aarti Singh. On the power of adaptivity\r\nin matrix completion and approximation. arXiv preprint arXiv:1407.3619\r\n(2014).\r\n[21] Ma, Jerry, and Denis Yarats. On the adequacy of untuned warmup for\r\nadaptive optimization. arXiv preprint arXiv:1910.04209 7 (2019).\r\n[22] M\u0131s\u0131r, Mustafa. Active matrix completion for algorithm selection.\r\nInternational Conference on Machine Learning, Optimization, and Data\r\nScience. Springer, Cham, 2019.\r\n[23] Paramythis, Alexandros, and Susanne Loidl-Reisinger. Adaptive learning\r\nenvironments and e-learning standards. Second european conference on\r\ne-learning. Vol. 1. No. 2003. 2003.\r\n[24] Ramazanli, Ilqar. Adaptive noisy matrix completion. arXiv preprint\r\narXiv:2203.08340 (2022).\r\n[25] Ramazanli, Ilqar. Lifelong matrix completion with sparsity-number.\r\narXiv preprint arXiv:2203.07637 (2022).\r\n[26] Ramazanli, Ilqar. Adaptive noisy matrix completion. arXiv preprint\r\narXiv:2203.08340 (2022).\r\n[27] Ramazanli, Ilqar, and Barnabas Poczos. Optimal exact matrix completion\r\nunder new parametrization. arXiv preprint arXiv:2002.02431 (2020).\r\n[28] Ramazanli, Ilqar, et al. Adaptive sampling distributed stochastic variance\r\nreduced gradient for heterogeneous distributed datasets. arXiv preprint\r\narXiv:2002.08528 (2020).\r\n[29] Recht, Benjamin. A simpler approach to matrix completion. Journal of\r\nMachine Learning Research 12.12 (2011).\r\n[30] Riedmiller, Martin, and Heinrich Braun. Rprop-a fast adaptive learning\r\nalgorithm. Proc. of ISCIS VII), Universitat. 1992.\r\n[31] Rohde, Angelika, and Alexandre B. Tsybakov. Estimation of\r\nhigh-dimensional low-rank matrices. The Annals of Statistics 39.2 (2011):\r\n887-930.\r\n[32] Ruchansky, Natali, Mark Crovella, and Evimaria Terzi. Matrix\r\ncompletion with queries. Proceedings of the 21th ACM SIGKDD\r\ninternational conference on knowledge discovery and data mining. 2015.\r\n[33] Settles, Burr. Active learning literature survey. (2009).\r\n[34] Xie, Kun, et al. Low cost and high accuracy data gathering in WSNs\r\nwith matrix completion. IEEE Transactions on Mobile Computing 17.7\r\n(2017): 1595-1608.\r\n[35] Zeiler, Matthew D. Adadelta: an adaptive learning rate method. arXiv\r\npreprint arXiv:1212.5701 (2012).\r\n[36] Zhao, R., et al. An Adaptive Curriculum Learning Framework\r\nfor Unbiased Glaucoma Diagnosis. Proceedings of the Computer\r\nVision\u2014ECCV (2020).\r\n[37] Zhang, Hui, et al. Strongly convex programming for exact matrix\r\ncompletion and robust principal component analysis. arXiv preprint\r\narXiv:1112.3946 (2011).\r\n[38] Arnold, Matthew, et al. A survey of adaptive optimization in virtual\r\nmachines. Proceedings of the IEEE 93.2 (2005): 449-466.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 186, 2022"}