Text

Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support

The problem of approximating a dense matrix by a product of sparse factors is a fundamental problem for many signal processing and machine learning tasks. It can be decomposed into two subproblems: finding the position of the nonzero coefficients in the sparse factors, and determining their values. While the first step is usually seen as the most challenging one due to its combinatorial nature, this paper focuses on the second step, referred to as sparse matrix approximation with fixed support. First, we show its NP-hardness, while also presenting a nontrivial family of supports making the problem practically tractable with a dedicated algorithm. Then we investigate the landscape of its natural optimization formulation, proving the absence of spurious local valleys and spurious local minima, whose presence could prevent local optimization methods to achieve global optimality. The advantages of the proposed algorithm over state-of-the-art first-order optimization methods are discussed.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS; Vol.44 No.2 April-June 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 503-529

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

LANDSCAPE
NP-HARDNESS
SPARSE MATRIX FACTORIZATION
FIXED SUPPORT

Info Detail Spesifik

https://doi.org/10.1137/22M1496657

Pernyataan Tanggungjawab

Quoc-Tung Le, Elisa Riccietti, Remi Gribonval

Versi lain/terkait

Lampiran Berkas

Komentar