Scalable Feature Matching Across Large Data Collections

References

• Ashburner, J. (2007), “A Fast Diffeomorphic Image Registration Algorithm,” NeuroImage, 38, 95–113. DOI: 10.1016/j.neuroimage.2007.07.007.
   PubMed Web of Science ®Google Scholar
• Balas, E., and Saltzman, M. J. (1991), “An Algorithm for the Three-Index Assignment Problem,” Operational Research, 39, 150–161. DOI: 10.1287/opre.39.1.150.
   Web of Science ®Google Scholar
• Bandelt, H.-J., Crama, Y., and Spieksma, F. C. R. (1994), “Approximation Algorithms for Multi-Dimensional Assignment Problems with Decomposable Costs,” Discrete Applied Mathematics, 49, 25–50. DOI: 10.1016/0166-218X(94)90199-6.
   Web of Science ®Google Scholar
• Bandelt, H.-J., Maas, A., and Spieksma, F. C. R. (2004), “Local Search Heuristics for Multi-Index Assignment Problems with Decomposable Costs,” Journal of the Operational Research Society, 55, 694–704. DOI: 10.1057/palgrave.jors.2601723.
   Web of Science ®Google Scholar
• Bar-Shalom, Y., Willett, P., and Tian, X. (2011), Tracking and Data Fusion: A Handbook of Algorithms, Storrs, CT: YBS Publishing.
   Google Scholar
• Basu, S., Davidson, I., and Wagstaff, K. L., eds. (2009), Constrained Clustering: Advances in Algorithms, Theory, and Applications, Chapman & Hall/CRC Data Mining and Knowledge Discovery Series, Boca Raton, FL: CRC Press.
   Google Scholar
• Bilenko, M., Basu, S., and Mooney, R. J. (2004), “Integrating Constraints and Metric Learning in Semi-supervised Clustering,” in ICML 2004, vol. 69, ACM, pp. 81–88. DOI: 10.1145/1015330.1015360.
   Google Scholar
• Birkhoff, G. (1946), “Tres observaciones sobre el algebra lineal [Three Observations on Linear Algebra],” Universidad Nacional de Tucuman. Revista Ser. A, 5, 147–151.
   Google Scholar
• Bleakley, K., and Vert, J.-P. (2011), “The Group Fused Lasso for Multiple Change-Point Detection,” Technical Report hal-00602121.
   Google Scholar
• Burkard, R., Dell’Amico, M., and Martello, S. (2009), Assignment Problems, Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM).
   Google Scholar
• Çela, E. (1998), The Quadratic Assignment Problem, vol. 1 of Combinatorial Optimization, Dordrecht: Kluwer Academic Publishers.
   Google Scholar
• Chang, C., and Glover, G. H. (2010), “Time-Frequency Dynamics of Resting-State Brain Connectivity Measured with fMRI,” Neuroimage, 50, 81–98. DOI: 10.1016/j.neuroimage.2009.12.011.
   PubMed Web of Science ®Google Scholar
• Collier, O., and Dalalyan, A. S. (2016), “Minimax Rates in Permutation Estimation for Feature Matching,” Journal of Machine Learning Research, 17, 1–31.
   Web of Science ®Google Scholar
• Collins, R. T. (2012), “Multitarget Data Association with Higher-Order Motion Models,” in Proceddings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1744–1751. DOI: 10.1109/CVPR.2012.6247870.
   Google Scholar
• Conte, D., Foggia, P., Sansone, C., and Vento, M. (2004), “Thirty Years of Graph Matching in Pattern Recognition,” International Journal of Pattern Recognition and Artificial Intelligence, 18, 265–298. DOI: 10.1142/S0218001404003228.
   Web of Science ®Google Scholar
• Craddock, C., Benhajali, Y., Chu, C., Chouinard, F., Evans, A., Jakab, A., Khundrakpam, B., Lewis, J., Li, Q., Milham, M., Yan, C., and Bellec, P. (2013), “The Neuro Bureau Preprocessing Initiative: Open Sharing of Preprocessed Neuroimaging Data and Derivatives,” Frontiers in Neuroinformatics, 7, doi:10.3389/conf.fninf.2013.09.00041.
   Google Scholar
• Degras, D. (2021), “Sparse Group Fused Lasso for Model Segmentation: A Hybrid Approach,” Advances in Data Analysis and Classification, 15, 625–671. DOI: 10.1007/s11634-020-00424-5.
   Web of Science ®Google Scholar
• DeGroot, M. H., and Goel, P. K. (1976), “The Matching Problem for Multivariate Normal Data,” Sankhyā Ser. B, 38, 14–29.
   Google Scholar
• Doherty, K., Fourie, D., and Leonard, J. (2019), “Multimodal Semantic SLAM with Probabilistic Data Association,” in Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), pp. 2419–2425. DOI: 10.1109/ICRA.2019.8794244.
   Google Scholar
• Drugan, M. M. (2015), “Generating QAP Instances with Known Optimum Solution and Additively Decomposable Cost Function,” Journal of Combinatorial Optimization, 30, 1138–1172. DOI: 10.1007/s10878-013-9689-6.
   Web of Science ®Google Scholar
• Frank, M., and Wolfe, P. (1956), “An Algorithm for Quadratic Programming,” Naval Research Logistics Quarterly, 3, 95–110. DOI: 10.1002/nav.3800030109.
   Google Scholar
• Friston, K., Moran, R., and Seth, A. K. (2013), “Analysing Connectivity with Granger Causality and Dynamic Causal Modelling,” Current Opinion in Neurobiology, 23, 172–178. DOI: 10.1016/j.conb.2012.11.010.
   PubMed Web of Science ®Google Scholar
• Gancarski, P., Dao, T.-B.-H., Crémilleux, B., Forestier, G., and Lampert, T. (2020), “Constrained Clustering: Current and New Trends,” in A Guided Tour of AI Research, eds. P. Marquis, O. Papini, H. Prade, pp. 447–484, Cham: Springer.
   Google Scholar
• Gendreau, M., and Potvin, J.-Y., eds. (2019), Handbook of Metaheuristics, vol. 272 of International Series in Operations Research and Management Science, Cham: Springer.
   Google Scholar
• Gutin, G., Goldengorin, B., and Huang, J. (2008), “Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems,” Journal of Heuristics, 14, 169–181. DOI: 10.1007/s10732-007-9033-3.
   Web of Science ®Google Scholar
• Handwerker, D. A., Roopchansingh, V., Gonzalez-Castillo, J., and Bandettini, P. A. (2012), “Periodic Changes in fMRI Connectivity,” Neuroimage, 63, 1712–1719. DOI: 10.1016/j.neuroimage.2012.06.078.
   PubMed Web of Science ®Google Scholar
• Haxby, J. V., Guntupalli, J. S., Connolly, A. C., Halchenko, Y. O., Conroy, B. R., Gobbini, M. I., Hanke, M., and Ramadge, P. J. (2011), “A Common, High-Dimensional Model of the Representational Space in Human Ventral Temporal Cortex,” Neuron, 72, 404–416. DOI: 10.1016/j.neuron.2011.08.026.
   PubMed Web of Science ®Google Scholar
• Hiep, T. K., Duc, N. M., and Trung, B. Q. (2016), “Local Search Approach for the Pairwise Constrained Clustering Problem,” in Proceedings of the 7th symposium on Information and Communication Technology (SoICT), ACM, pp. 115–122.
   Google Scholar
• Hsu, D., Shi, K., and Sun, X. (2017), “Linear Regression Without Correspondence,” in Advances in Neural Information Processing Systems, vol. 30, Curran Associates, Inc., pp. 1531–1540.
   Google Scholar
• Hutchison, R. M., Womelsdorf, T., Allen, E. A., Bandettini, P. A., Calhoun, V. D., Corbetta, M., Della Penna, S., Duyn, J. H., Glover, G. H., Gonzalez-Castillo, J., Handwerker, D. A., Keilholz, S., Kiviniemi, V., Leopold, D. A., de Pasquale, F., Sporns, O., Walter, M., and Chang, C. (2013), “Dynamic Functional Connectivity: Promise, Issues, and Interpretations,” Neuroimage, 80, 360–378. DOI: 10.1016/j.neuroimage.2013.05.079.
   PubMed Web of Science ®Google Scholar
• Jerrum, M., Sinclair, A., and Vigoda, E. (2004), “A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries,” Journal of the ACM, 51, 671–697. DOI: 10.1145/1008731.1008738.
   Web of Science ®Google Scholar
• Karapetyan, D., and Gutin, G. (2011), “Local Search Heuristics for the Multidimensional Assignment Problem,” Journal of Heuristics, 17, 201–249. DOI: 10.1007/s10732-010-9133-3.
   Web of Science ®Google Scholar
• Kim, D. (2008), “Mixture Inference at the Edge of Identifiability,” PhD thesis, Pennsylvania State University.
   Google Scholar
• Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., Lü, Z., Wang, H., and Wang, Y. (2014), “The Unconstrained Binary Quadratic Programming Problem: A Survey,” Journal of Combinatorial Optimization, 28, 58–81. DOI: 10.1007/s10878-014-9734-0.
   Web of Science ®Google Scholar
• Koopmans, T. C., and Beckmann, M. (1957), “Assignment Problems and the Location of Economic Activities,” Econometrica, 25, 53–76. DOI: 10.2307/1907742.
   Web of Science ®Google Scholar
• Kuck, J., Dao, T., Rezatofighi, H., Sabharwal, A., and Ermon, S. (2019), “Approximating the Permanent by Sampling from Adaptive Partitions,” in Advances in Neural Information Processing Systems, vol. 32, Curran Associates, Inc., pp. 8860–8871.
   Google Scholar
• Kuhn, H. W. (1955), “The Hungarian Method for the Assignment Problem,” Naval Research Logistics Quarterly, 2, 83–97. DOI: 10.1002/nav.3800020109.
   Google Scholar
• Kuroki, Y., and Matsui, T. (2009), “An Approximation Algorithm for Multidimensional Assignment Problems Minimizing the Sum of Squared Errors,” Discrete Applied Mathematics, 157, 2124–2135. DOI: 10.1016/j.dam.2007.10.013.
   Web of Science ®Google Scholar
• Lacoste-Julien, S. (2016), “Convergence Rate of Frank-Wolfe for Non-convex Objectives,” arXiv e-prints, 1607.00345.
   Google Scholar
• Le Moigne, J., Netanyahu, N., and Eastman, R. (2011), Image Registration for Remote Sensing, Cambridge: Cambridge University Press.
   Google Scholar
• Lloyd, S. P. (1982), “Least Squares Quantization in PCM,” IEEE Transactions on Information Theory, 28, 129–137. DOI: 10.1109/TIT.1982.1056489.
   Web of Science ®Google Scholar
• Lowe, D. (2001), “Local Feature View Clustering for 3D Object Recognition,” in Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), vol. 1, pp. I–I.
   Google Scholar
• Lyzinski, V., Fishkind, D. E., Fiori, M., Vogelstein, J. T., Priebe, C. E., and Sapiro, G. (2016), “Graph Matching: Relax at Your Own Risk,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 38, 60–73. DOI: 10.1109/TPAMI.2015.2424894.
   PubMed Web of Science ®Google Scholar
• McLachlan, G., and Peel, D. (2000), Finite Mixture Models, Wiley Series in Probability and Statistics: Applied Probability and Statistics, New York: Wiley-Interscience.
   Google Scholar
• Munkres, J. (1957), “Algorithms for the Assignment and Transportation Problems,” Journal of the Society for Industrial and Applied Mathematics, 5, 32–38. DOI: 10.1137/0105003.
   Google Scholar
• Murty, K. G. (1968), “An Algorithm for Ranking all the Assignments in Order of Increasing Cost,” Operational Research, 16, 682–687. DOI: 10.1287/opre.16.3.682.
   Web of Science ®Google Scholar
• Natu, S., Date, K., and Nagi, R. (2020), “GPU-Accelerated Lagrangian Heuristic for Multidimensional Assignment Problems with Decomposable Costs,” Parallel Computing, 97, 102666. DOI: 10.1016/j.parco.2020.102666.
   Web of Science ®Google Scholar
• Nijenhuis, A., and Wilf, H. S. (1978), Combinatorial Algorithms (2nd ed.), New York-London: Academic Press, Inc.
   Google Scholar
• Oliveira, C. A. S., and Pardalos, P. M. (2004), “Randomized Parallel Algorithms for the Multidimensional Assignment Problem,” Applied Numerical Mathematics, 49, 117–133. DOI: 10.1016/j.apnum.2003.11.014.
   Web of Science ®Google Scholar
• Pananjady, A., Wainwright, M. J., and Courtade, T. A. (2018), “Linear Regression with Shuffled Data: Statistical and Computational Limits of Permutation Recovery,” IEEE Transactions on Information Theory, 64, 3286–3300. DOI: 10.1109/TIT.2017.2776217.
   Web of Science ®Google Scholar
• Pardalos, P. M., and Pitsoulis, L. S., eds. (2000), Nonlinear Assignment Problems, vol. 7 of Combinatorial Optimization, Dordrecht: Kluwer Academic Publishers.
   Google Scholar
• Pelleg, D., and Baras, D. (2007), “K-means with Large and Noisy Constraint Sets,” in Proceddings of the 18th European Conference on Machine Learning ECML), Springer, pp. 674–682.
   Google Scholar
• Pierskalla, W. P. (1968), “The Multidimensional Assignment Problem,” Operational Research, 16, 422–431. DOI: 10.1287/opre.16.2.422.
   Web of Science ®Google Scholar
• Poore, A. P., and Rijavec, N. (1993), “A Lagrangian Relaxation Algorithm for Multidimensional Assignment Problems Arising from Multitarget Tracking,” SIAM Journal on Optimization, 3, 544–563. DOI: 10.1137/0803027.
   Web of Science ®Google Scholar
• Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (3rd ed.), Cambridge: Cambridge University Press.
   Google Scholar
• Rand, W. M. (1971), “Objective Criteria for the Evaluation of Clustering Methods,” Journal of the American Statistical Association, 66, 846–850. DOI: 10.1080/01621459.1971.10482356.
   Web of Science ®Google Scholar
• Rasero, J., Diez, I., Cortes, J. M., Marinazzo, D., and Stramaglia, S. (2019), “Connectome Sorting by Consensus Clustering Increases Separability in Group Neuroimaging Studies,” Nature Neuroscience, 3, 325–343.
   Google Scholar
• Rezatofighi, S. H., Milan, A., Zhang, Z., Shi, Q., Dick, A., and Reid, I. (2015), “Joint Probabilistic Data Association Revisited,” in Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV), pp. 3047–3055. DOI: 10.1109/ICCV.2015.349.
   Google Scholar
• Robertson, A. J. (2001), “A Set of Greedy Randomized Adaptive Local Search Procedure (GRASP) Implementations for the Multidimensional Assignment Problem,” Computational Optimization and Applications, 19, 145–164.
   Web of Science ®Google Scholar
• Ryser, H. J. (1963), Combinatorial Mathematics, vol. 14 of The Carus Mathematical Monographs, New York: Wiley.
   Google Scholar
• Shalom, M., Wong, P. W. H., and Zaks, S. (2010), “On-line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology,” in Structural Information and Communication Complexity, vol. 5869 of Lecture Notes in Computer Science, pp. 281–294, Berlin: Springer.
   Google Scholar
• Shental, N., Bar-hillel, A., Hertz, T., and Weinshall, D. (2004), “Computing Gaussian Mixture Models with EM Using Equivalence Constraints,” in Advances in Neural Information Processing Systems, vol. 16, MIT Press, pp. 465–472.
   Google Scholar
• Sinkhorn, R. (1964), “A Relationship Between Arbitrary Positive Mmatrices and Doubly Stochastic Matrices,” Annals of Mathematical Statistics, 35, 876–879. DOI: 10.1214/aoms/1177703591.
   Google Scholar
• Spieksma, F., and Woeginger, G. (1996), “Geometric Three-Dimensional Assignment Problems,” European Journal of Operational Research, 91, 611–618. DOI: 10.1016/0377-2217(95)00003-8.
   Web of Science ®Google Scholar
• Tauer, G., and Nagi, R. (2013), “A Map-reduce Lagrangian Heuristic for Multidimensional Assignment Problems with Decomposable Costs,” Parallel Computing, 39, 653–668. DOI: 10.1016/j.parco.2013.08.012.
   Web of Science ®Google Scholar
• Tibshirani, R. (1996), “Regression Shrinkage and Selection via the Lasso,” Journal of the Royal Statistical Society, Series B, 58, 267–288. DOI: 10.1111/j.2517-6161.1996.tb02080.x.
   Google Scholar
• Ting, C. M., Ombao, H., Samdin, S. B., and Salleh, S. H. (2018), “Estimating Dynamic Connectivity States in fMRI Using Regime-Switching Factor Mmodels,” IEEE Transactions on Medical Imaging, 37, 1011–1023. DOI: 10.1109/TMI.2017.2780185.
   PubMed Web of Science ®Google Scholar
• Uhlmann, J. K. (2004), “Matrix Permanent Inequalities for Approximating Joint Assignment Matrices in Tracking Systems,” Journal of The Franklin Institute, 341, 569–593. DOI: 10.1016/j.jfranklin.2004.07.003.
   Web of Science ®Google Scholar
• Valdés-Sosa, P. A., Sánchez-Bornot, J. M., Lage-Castellanos, A., Vega-Hernández, M., Bosch-Bayard, J., Melie-García, L., and Canales-Rodríguez, E. (2005), “Estimating Brain Functional Connectivity with Sparse Multivariate Autoregression,” Philosophical Transactions of the Royal Society B, 360, 969–981. DOI: 10.1098/rstb.2005.1654.
   PubMed Web of Science ®Google Scholar
• Vogelstein, J. T., Conroy, J. M., Lyzinski, V., Podrazik, L. J., Kratzer, S. G., Harley, E. T., Fishkind, D. E., Vogelstein, R. J., and Priebe, C. E. (2015), “Fast Approximate Quadratic Programming for Graph Matching,” PloS One, 10, 1–17. DOI: 10.1371/journal.pone.0121002.
   Web of Science ®Google Scholar
• von Neumann, J. (1953), “A Certain Zero-Sum Two-Person Game Equivalent to the Optimal Assignment Problem,” in Contributions to the Theory of Games, vol. 2, Annals of Mathematics Studies, no. 28, pp. 5–12, Princeton, NJ: Princeton University Press.
   Google Scholar
• Wagstaff, K., Cardie, C., Rogers, S., and Schrödl, S. (2001), “Constrained k-means Clustering with Background Knowledge,” in Proceedings of the 18th International Conference on Machine Learning (ICML), pp. 577–584.
   Google Scholar
• Wang, L., Liu, T., Wang, G., Chan, K. L., and Yang, Q. (2015), “Video Tracking Using Learned Hierarchical Features,” IEEE Transactions on Image Processing, 24, 1424–1435. DOI: 10.1109/TIP.2015.2403231.
   PubMed Web of Science ®Google Scholar
• Wright, S. J. (2015), “Coordinate Descent Algorithms,” Mathematical Programming, 151, 3–34. DOI: 10.1007/s10107-015-0892-3.
   Web of Science ®Google Scholar