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

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

Author

Listed:
  • GILLIS, Nicolas
  • GLINEUR, François

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).
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • GILLIS, Nicolas & GLINEUR, François, 2011. "Low-rank matrix approximation with weights or missing data is NP-hard," LIDAM Reprints CORE 2382, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvrp:2382
    DOI: 10.1137/110820361
    Note: In : SIAM Journal on Matrix Analysis and Applications, 32(4), 1149-1165, 2011
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Other versions of this item:

    References listed on IDEAS

    as
    1. 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).
    2. 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.
    3. Rabah Amir, 2005. "Supermodularity and Complementarity in Economics: An Elementary Survey," Southern Economic Journal, John Wiley & Sons, vol. 71(3), pages 636-660, January.
    4. 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.
    5. Huriot,Jean-Marie & Thisse,Jacques-François (ed.), 2009. "Economics of Cities," Cambridge Books, Cambridge University Press, number 9780521118279.
    6. Belleflamme,Paul & Peitz,Martin, 2015. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9781107069978.
    7. Winfried Pohlmeier & Luc Bauwens & David Veredas, 2007. "High frequency financial econometrics. Recent developments," ULB Institutional Repository 2013/136223, ULB -- Universite Libre de Bruxelles.
    8. Markovsky, Ivan & Niranjan, Mahesan, 2010. "Approximate low-rank factorization with structured factors," Computational Statistics & Data Analysis, Elsevier, vol. 54(12), pages 3411-3420, December.
    9. Luc Bauwens & Winfried Pohlmeier & David Veredas (ed.), 2008. "High Frequency Financial Econometrics," Studies in Empirical Economics, Springer, number 978-3-7908-1992-2, April.
    10. Belleflamme,Paul & Peitz,Martin, 2015. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9781107687899.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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).
    8. Moreno-Ternero, Juan D., 2011. "Voting over piece-wise linear tax methods," Journal of Mathematical Economics, Elsevier, vol. 47(1), pages 29-36, January.
    9. Leroux, Marie-Louise & Ponthiere, Gregory, 2013. "Utilitarianism and unequal longevities: A remedy?," Economic Modelling, Elsevier, vol. 30(C), pages 888-899.
    10. 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.
    11. 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).
    12. LUTTENS, Roland Iwan, 2010. "Lower bounds rule!," LIDAM Discussion Papers CORE 2010069, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Florens, Jean-Pierre & Schwarz, Maik & Van Bellegem, Sébastien, 2010. "Nonparametric Frontier Estimation from Noisy Data," TSE Working Papers 10-179, Toulouse School of Economics (TSE).
    14. 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).
    15. GABSZEWICZ, Jean & TAROLA, Ornella, 2010. "Product innovation and market acquisition of firms," LIDAM Discussion Papers CORE 2010078, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. 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.
    17. MIYAGIWA, Kaz & SONG, Huasheng & VANDENBUSSCHE, Hylke, 2010. "Innovation, antidumping and retaliation," LIDAM Discussion Papers CORE 2010064, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    18. GILLIS, Nicolas & GLINEUR, François, 2010. "A multilevel approach for nonnegative matrix factorization," LIDAM Discussion Papers CORE 2010047, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. 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.
    20. HINDRIKS, Jean & VERSCHELDE, Marijn & RAYP, Glenn & SCHOORS, Koen, 2010. "School autonomy and educational performance: within-country evidence," LIDAM Discussion Papers CORE 2010082, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    More about this item

    Statistics

    Access and download statistics

    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:louvrp:2382. 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.