{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T14:02:10Z","timestamp":1762351330576,"version":"build-2065373602"},"reference-count":56,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2022,5,31]],"date-time":"2022-05-31T00:00:00Z","timestamp":1653955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Faculty of Science and Technology","award":["SciGR 12\/2565"],"award-info":[{"award-number":["SciGR 12\/2565"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>An accelerated least-squares approach is introduced in this work by incorporating a greedy point selection method with randomized singular value decomposition (rSVD) to reduce the computational complexity of missing data reconstruction. The rSVD is used to speed up the computation of a low-dimensional basis that is required for the least-squares projection by employing randomness to generate a small matrix instead of a large matrix from high-dimensional data. A greedy point selection algorithm, based on the discrete empirical interpolation method, is then used to speed up the reconstruction process in the least-squares approximation. The accuracy and computational time reduction of the proposed method are demonstrated through three numerical experiments. The first two experiments consider standard testing images with missing pixels uniformly distributed on them, and the last numerical experiment considers a sequence of many incomplete two-dimensional miscible flow images. The proposed method is shown to accelerate the reconstruction process while maintaining roughly the same order of accuracy when compared to the standard least-squares approach.<\/jats:p>","DOI":"10.3390\/a15060190","type":"journal-article","created":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T03:33:18Z","timestamp":1654054398000},"page":"190","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Missing Data Reconstruction Method Using an Accelerated Least-Squares Approximation with Randomized SVD"],"prefix":"10.3390","volume":"15","author":[{"given":"Siriwan","family":"Intawichai","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathum Thani 12120, Thailand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5824-5519","authenticated-orcid":false,"given":"Saifon","family":"Chaturantabut","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathum Thani 12120, Thailand"}]}],"member":"1968","published-online":{"date-parts":[[2022,5,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"4274","DOI":"10.1109\/TGRS.2018.2810208","article-title":"Missing data reconstruction in remote sensing image with a unified spatial\u2013temporal\u2013spectral deep convolutional neural network","volume":"56","author":"Zhang","year":"2018","journal-title":"IEEE Trans. Geosci. Remote Sens."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"3302","DOI":"10.1038\/s41598-020-59801-x","article-title":"Deep learning for irregularly and regularly missing data reconstruction","volume":"10","author":"Chai","year":"2020","journal-title":"Sci. Rep."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.asoc.2014.09.038","article-title":"Reconstruction of missing data in multidimensional time series by fuzzy similarity","volume":"26","author":"Baraldi","year":"2015","journal-title":"Appl. Soft Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1080\/15481603.2022.2031549","article-title":"For-backward LSTM-based missing data reconstruction for time-series Landsat images","volume":"59","author":"Zhou","year":"2022","journal-title":"Gisci. Remote Sens."},{"key":"ref_5","unstructured":"Hafner, J.L., Deenadhayalan, V., Rao, K., and Tomlin, J.A. (2005). Matrix Methods for Lost Data Reconstruction in Erasure Codes, USENIX Association."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"V273","DOI":"10.1190\/geo2013-0022.1","article-title":"Tensor completion based on nuclear norm minimization for 5D seismic data reconstruction","volume":"78","author":"Kreimer","year":"2013","journal-title":"Geophysics"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1016\/j.asoc.2018.07.027","article-title":"Wind power prediction with missing data using Gaussian process regression and multiple imputation","volume":"71","author":"Liu","year":"2018","journal-title":"Appl. Soft Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.knosys.2016.06.012","article-title":"kNN-IS: An Iterative Spark-based design of the k-Nearest Neighbors classifier for big data","volume":"117","author":"Maillo","year":"2017","journal-title":"Knowl. Based Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.knosys.2015.06.022","article-title":"Classification of incomplete data based on belief functions and K-nearest neighbors","volume":"89","author":"Liu","year":"2015","journal-title":"Knowl.-Based Syst."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3887","DOI":"10.1093\/bioinformatics\/bti634","article-title":"Non-linear PCA: A missing data approach","volume":"21","author":"Scholz","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"e34","DOI":"10.1093\/nar\/gnh026","article-title":"LSimpute: Accurate estimation of missing values in microarray data with least squares methods","volume":"32","author":"Dysvik","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"6052","DOI":"10.1364\/AO.55.006052","article-title":"Least-squares method for data reconstruction from gradient data in deflectometry","volume":"55","author":"Ren","year":"2016","journal-title":"Appl. Opt."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"WB121","DOI":"10.1190\/1.3478375","article-title":"Data reconstruction with shot-profile least-squares migration","volume":"75","author":"Kaplan","year":"2010","journal-title":"Geophysics"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1146\/annurev.fl.25.010193.002543","article-title":"The proper orthogonal decomposition in the analysis of turbulent flows","volume":"25","author":"Berkooz","year":"1993","journal-title":"Annual Rev. Fluid Mech."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1811","DOI":"10.1088\/0964-1726\/15\/6\/036","article-title":"Damage detection and localization for continuous static monitoring of structures using a proper orthogonal decomposition of signals","volume":"15","author":"Lanata","year":"2006","journal-title":"Smart Mater. Struct."},{"key":"ref_16","unstructured":"Schenone, E. (2014). Reduced Order Models, Forward and Inverse Problems in Cardiac Electrophysiology. [Ph.D. Thesis, Universit\u00e9 Pierre et Marie Curie]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1016\/j.ijheatfluidflow.2006.01.001","article-title":"POD of vorticity fields: A method for spatial characterization of coherent structures","volume":"27","author":"Gurka","year":"2006","journal-title":"Int. J. Heat Fluid Flow"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1007\/s00704-019-02898-6","article-title":"Gappy POD-based reconstruction of the temperature field in Tibet","volume":"138","author":"Xu","year":"2019","journal-title":"Theor. Appl. Climatol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1505","DOI":"10.2514\/1.2159","article-title":"Aerodynamic Data Reconstruction and Inverse Design Using Proper Orthogonal Decomposition","volume":"42","author":"Damodaran","year":"2004","journal-title":"AIAA"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1016\/S1570-7946(09)70173-7","article-title":"Reconstruction of flame kinematics and analysis of cycle variation in a Spark Ignition Engine by means of Proper Orthogonal Decomposition","volume":"26","author":"Bizon","year":"2009","journal-title":"Comput. Aided Chem. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"20731","DOI":"10.1016\/j.ijhydene.2016.09.201","article-title":"Investigation into the combustion instability of synthetic natural gases using high speed flame images and their proper orthogonal decomposition","volume":"41","author":"Choi","year":"2016","journal-title":"Int. J. Hydrog. Energy"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1016\/j.crme.2009.10.003","article-title":"Note on the POD-based time interpolation from successive PIV images","volume":"337","author":"Bouhoubeiny","year":"2009","journal-title":"Comptes Rendus M\u00e9Canique"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/j.cma.2015.01.001","article-title":"A computationally efficient approach for inverse material characterization combining Gappy {POD} with direct inversion","volume":"286","author":"Wang","year":"2015","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"6925","DOI":"10.1016\/j.apm.2015.02.036","article-title":"Dynamic reconstruction algorithm for electrical capacitance tomography based on the proper orthogonal decomposition","volume":"39","author":"Lei","year":"2015","journal-title":"Appl. Math. Model."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.cam.2017.01.020","article-title":"Optimal control of water flooding reservoir using proper orthogonal decomposition","volume":"320","author":"Sun","year":"2017","journal-title":"J. Comput. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1137\/090771806","article-title":"Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions","volume":"53","author":"Halko","year":"2011","journal-title":"SIAM Rev."},{"key":"ref_27","unstructured":"Ji, H., Yu, W., and Li, Y. (2016). A Rank Revealing Randomized Singular Value Decomposition (R3SVD) Algorithm for Low-rank Matrix Approximations. arXiv."},{"key":"ref_28","first-page":"2737","article-title":"Randomized SVD Methods in Hyperspectral Imaging","volume":"2012","author":"Zhang","year":"2012","journal-title":"J. Electr. Comput. Eng."},{"key":"ref_29","unstructured":"Ji, H., and Li, Y. (2014, January 17). GPU Accelerated Randomized Singular Value Decomposition and Its Application in Image Compression. Proceedings of the MSVESCC, Suffolk, VA, USA."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Intawichai, S., and Chaturantabut, S. (2020, January 17\u201318). Missing Image Data Reconstruction Based on Least-Squares Approach with Randomized SVD. Proceedings of the International Conference on Intelligent Computing & Optimization, Koh Samui, Thailand.","DOI":"10.1007\/978-3-030-68154-8_89"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1339","DOI":"10.1137\/17M1141977","article-title":"Efficient randomized algorithms for the fixed-precision low-rank matrix approximation","volume":"39","author":"Yu","year":"2018","journal-title":"Siam J. Matrix Anal. Appl."},{"key":"ref_32","unstructured":"Voronin, S., and Martinsson, P.G. (2015). RSVDPACK: An implementation of randomized algorithms for computing the singular value, interpolative, and CUR decompositions of matrices on multi-core and GPU architectures. arXiv."},{"key":"ref_33","first-page":"1396","article-title":"Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition","volume":"Volume 1","author":"Musco","year":"2015","journal-title":"Proceedings of the 28th International Conference on Neural Information Processing Systems"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3004053","article-title":"Algorithm 971: An implementation of a randomized algorithm for principal component analysis","volume":"43","author":"Li","year":"2017","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2737","DOI":"10.1137\/090766498","article-title":"Nonlinear Model Reduction via Discrete Empirical Interpolation","volume":"32","author":"Chaturantabut","year":"2010","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"A311","DOI":"10.1137\/120899042","article-title":"A posteriori error estimation for DEIM reduced nonlinear dynamical systems","volume":"36","author":"Wirtz","year":"2014","journal-title":"Siam J. Sci. Comput."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"615","DOI":"10.34768\/amcs-2020-0045","article-title":"Stabilized model reduction for nonlinear dynamical systems through a contractivity-preserving framework","volume":"30","author":"Chaturantabut","year":"2020","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.jcp.2012.11.035","article-title":"POD\/DEIM nonlinear model order reduction of an ADI implicit shallow water equations model","volume":"237","author":"Navon","year":"2013","journal-title":"J. Comput. Phys."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1016\/j.jcp.2015.04.030","article-title":"POD\/DEIM Strategies for reduced data assimilation systems","volume":"295","author":"Stefanescu","year":"2014","journal-title":"J. Comput. Phys."},{"key":"ref_40","unstructured":"Feng, Z., and Soulaimani, A. (June, January 30). Reduced Order Modelling Based on POD Method for 3D Nonlinear Aeroelasticity. Proceedings of the 18th IASTED International Conference on Modelling and Simulation, Montreal, QC, Canada."},{"key":"ref_41","first-page":"2053","article-title":"Reduced-Order Modeling of a Local Discontinuous Galerkin Method for Burgers-Poisson Equations","volume":"18","author":"Ploymaklam","year":"2020","journal-title":"Thai J. Math."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcp.2014.01.011","article-title":"Non-linear model reduction for the Navier\u2013Stokes equations using residual DEIM method","volume":"263","author":"Xiao","year":"2014","journal-title":"J. Comput. Phys."},{"key":"ref_43","unstructured":"Chaturantabut, S. (2017, January 21\u201322). Accelerated POD least-squares approach for missing data reconstruction. Proceedings of the 17th International Conference on Mathematical Methods in Science and Engineering, Beijing, China."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF02288367","article-title":"The approximation of one matrix by another of lower rank","volume":"1","author":"Eckart","year":"1936","journal-title":"Psychometrika"},{"key":"ref_45","unstructured":"Volkwein, S. (2013). Proper Orthogonal Decomposition: Theory and Reduced-Order Modelling, University of Konstanz. Lecture Notes."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1137\/0917055","article-title":"Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization","volume":"17","author":"Gu","year":"1996","journal-title":"Siam J. Sci. Comput."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Lawson, C.L., and Hanson, R.J. (1995). Solving Least Squares Problems, SIAM.","DOI":"10.1137\/1.9781611971217"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/BF01436075","article-title":"Numerical methods for solving linear least squares problems","volume":"7","author":"Golub","year":"1965","journal-title":"Numer. Math."},{"key":"ref_49","unstructured":"Lee, D.Q. (2012). Numerically Efficient Methods for Solving Least Squares Problems, Pennsylvania State University."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Gu, Z., Lin, W., Lee, B.S., Lau, C.T., and Paul, M. (2010, January 11\u201312). Two dimensional singular value decomposition (2D-SVD) based video coding. Proceedings of the 2010 IEEE International Conference on Image Processing, Haikou, China.","DOI":"10.1109\/ICIP.2010.5650998"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"2731","DOI":"10.1016\/j.neucom.2008.09.020","article-title":"Combined projection and kernel basis functions for classification in evolutionary neural networks","volume":"72","author":"Carbonero","year":"2009","journal-title":"Neurocomputing"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1111\/j.1467-8659.2009.01393.x","article-title":"Wind projection basis for real-time animation of trees","volume":"Volume 28","author":"Diener","year":"2009","journal-title":"Computer Graphics Forum"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/s00466-005-0667-4","article-title":"Radial point interpolation collocation method (RPICM) for the solution of nonlinear Poisson problems","volume":"36","author":"Liu","year":"2005","journal-title":"Comput. Mech."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Weickert, J., and Welk, M. (2006). Tensor field interpolation with PDEs. Visualization and Processing of Rensor Fields, Springer.","DOI":"10.1007\/3-540-31272-2"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1002\/nme.2086","article-title":"A \u2018best points\u2019 interpolation method for efficient approximation of parametrized functions","volume":"73","author":"Nguyen","year":"2008","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1080\/10236190801953864","article-title":"Approximate solution of multipoint boundary value problems for linear differential equations by polynomial functions","volume":"14","author":"Groza","year":"2008","journal-title":"J. Differ. Equ. Appl."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/190\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:22:52Z","timestamp":1760138572000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/190"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,31]]},"references-count":56,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["a15060190"],"URL":"https:\/\/doi.org\/10.3390\/a15060190","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,5,31]]}}}