IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2010075.html
   My bibliography  Save this paper

Low-rank matrix approximation with weights or missing data is NP-hard

Author

Listed:
  • GILLIS, Nicolas

    (Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium)

  • GLINEUR, François

    (Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium)

Abstract

Weighted low-rank approximation (WLRA), a dimensionality reduction technique for data analysis, has been successfully used in several applications, such as in collaborative filtering to design recommender systems or in computer vision to recover structure from motion. In this paper, we study the computational complexity of WLRA and prove that it is NP-hard to find an approximate solution, even when a rank-one approximation is sought. Our proofs are based on a reduction from the maximum-edge biclique problem, and apply to strictly positive weights as well as binary weights (the latter corresponding to low-rank matrix approximation with missing data).

Suggested Citation

  • GILLIS, Nicolas & GLINEUR, François, 2010. "Low-rank matrix approximation with weights or missing data is NP-hard," LIDAM Discussion Papers CORE 2010075, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2010075
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2010.html
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Belleflamme,Paul & Peitz,Martin, 2015. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9781107687899, September.
    2. GILLIS, Nicolas & GLINEUR, François, 2008. "Nonnegative factorization and the maximum edge biclique problem," LIDAM Discussion Papers CORE 2008064, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Pierre-Philippe Combes & Thierry Mayer & Jacques-François Thisse, 2008. "Economic Geography: The Integration of Regions and Nations," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-00311000, HAL.
    4. Winfried Pohlmeier & Luc Bauwens & David Veredas, 2007. "High frequency financial econometrics. Recent developments," ULB Institutional Repository 2013/136223, ULB -- Universite Libre de Bruxelles.
    5. Peeters, M.J.P., 2003. "The maximum edge biclique problem is NP-complete," Other publications TiSEM 3e340431-37b3-4bc5-9b14-9, Tilburg University, School of Economics and Management.
    6. Rabah Amir, 2005. "Supermodularity and Complementarity in Economics: An Elementary Survey," Southern Economic Journal, John Wiley & Sons, vol. 71(3), pages 636-660, January.
    7. Markovsky, Ivan & Niranjan, Mahesan, 2010. "Approximate low-rank factorization with structured factors," Computational Statistics & Data Analysis, Elsevier, vol. 54(12), pages 3411-3420, December.
    8. Huriot,Jean-Marie & Thisse,Jacques-François (ed.), 2009. "Economics of Cities," Cambridge Books, Cambridge University Press, number 9780521118279, October.
    9. Luc Bauwens & Winfried Pohlmeier & David Veredas (ed.), 2008. "High Frequency Financial Econometrics," Studies in Empirical Economics, Springer, number 978-3-7908-1992-2, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gillard, Jonathan & Usevich, Konstantin, 2018. "Structured low-rank matrix completion for forecasting in time series analysis," International Journal of Forecasting, Elsevier, vol. 34(4), pages 582-597.
    2. Nicolas Gillis & Stephen A. Vavasis, 2018. "On the Complexity of Robust PCA and ℓ 1 -Norm Low-Rank Matrix Approximation," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1072-1084, November.
    3. Glover, Fred & Ye, Tao & Punnen, Abraham P. & Kochenberger, Gary, 2015. "Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs," European Journal of Operational Research, Elsevier, vol. 241(3), pages 697-707.
    4. Qinghua Wu & Yang Wang & Fred Glover, 2020. "Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 74-89, January.
    5. Namgil Lee & Jong-Min Kim, 2018. "Block tensor train decomposition for missing data estimation," Statistical Papers, Springer, vol. 59(4), pages 1283-1305, December.
    6. Zhikai Yang & Le Han, 2023. "A global exact penalty for rank-constrained optimization problem and applications," Computational Optimization and Applications, Springer, vol. 84(2), pages 477-508, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. GILLIS, Nicolas & GLINEUR, François, 2010. "On the geometric interpretation of the nonnegative rank," LIDAM Discussion Papers CORE 2010051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Gautier, Axel & Wauthy, Xavier, 2012. "Competitively neutral universal service obligations," Information Economics and Policy, Elsevier, vol. 24(3), pages 254-261.
    3. Pierre Pestieau & Maria Racionero, 2015. "Tagging with leisure needs," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 687-706, December.
    4. Bréchet, Thierry & Jouvet, Pierre-André & Rotillon, Gilles, 2013. "Tradable pollution permits in dynamic general equilibrium: Can optimality and acceptability be reconciled?," Ecological Economics, Elsevier, vol. 91(C), pages 89-97.
    5. Cremer, Helmuth & Gahvari, Firouz & Pestieau, Pierre, 2011. "Fertility, human capital accumulation, and the pension system," Journal of Public Economics, Elsevier, vol. 95(11), pages 1272-1279.
    6. Leroux, Marie-Louise & Ponthiere, Gregory, 2013. "Utilitarianism and unequal longevities: A remedy?," Economic Modelling, Elsevier, vol. 30(C), pages 888-899.
    7. A. Mauleon & Vincent Vannetelbosch & Cecilia Vergari, 2014. "Unions' Relative Concerns And Strikes In Wage Bargaining," Bulletin of Economic Research, Wiley Blackwell, vol. 66(4), pages 374-383, October.
    8. M.-L. Leroux & P. Pestieau, 2012. "The political economy of derived pension rights," International Tax and Public Finance, Springer;International Institute of Public Finance, vol. 19(5), pages 753-776, October.
    9. Per J. Agrell & Axel Gautier, 2017. "A Theory of Soft Capture," Scandinavian Journal of Economics, Wiley Blackwell, vol. 119(3), pages 571-596, July.
    10. Manzi, Jorge & San Martin, Ernesto & Van Bellegem, Sébastien, 2010. "School System Evaluation By Value-Added Analysis under Endogeneity," IDEI Working Papers 631, Institut d'Économie Industrielle (IDEI), Toulouse.
    11. Michel Le Breton & Juan Moreno-Ternero & Alexei Savvateev & Shlomo Weber, 2013. "Stability and fairness in models with a multiple membership," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 673-694, August.
    12. Florens, Jean-Pierre & Schwarz, Maik & Van Bellegem, Sébastien, 2010. "Nonparametric Frontier Estimation from Noisy Data," IDEI Working Papers 625, Institut d'Économie Industrielle (IDEI), Toulouse.
    13. STEPHAN, Rüdiger, 2010. "An extension of disjunctive programming and its impact for compact tree formulations," LIDAM Discussion Papers CORE 2010045, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Moreno-Ternero, Juan D., 2011. "Voting over piece-wise linear tax methods," Journal of Mathematical Economics, Elsevier, vol. 47(1), pages 29-36, January.
    15. Rombouts, Jeroen V.K. & Stentoft, Lars, 2015. "Option pricing with asymmetric heteroskedastic normal mixture models," International Journal of Forecasting, Elsevier, vol. 31(3), pages 635-650.
    16. AGRELL, Per & KASPERZEC, Roman, 2010. "Dynamic joint investments in supply chains under information asymmetry," LIDAM Discussion Papers CORE 2010085, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    17. DI SUMMA, Marco & WOLSEY, Laurence, 2010. "Mixing sets linked by bidirected paths," LIDAM Discussion Papers CORE 2010063, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    18. LUTTENS, Roland Iwan, 2010. "Lower bounds rule!," LIDAM Discussion Papers CORE 2010069, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. DENUIT, Michel & EECKHOUDT, Louis & TSETLIN, Ilia & WINKLER, Robert L., 2010. "Multivariate concave and convex stochastic dominance," LIDAM Discussion Papers CORE 2010044, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Johannes, Jan & Van Bellegem, Sébastien & Vanhems, Anne, 2010. "Iterative Regularization in Nonparametric Instrumental Regression," TSE Working Papers 10-184, Toulouse School of Economics (TSE).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2010075. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.