Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Spurious Valleys, Spurious Minima and NP-hardness 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 non-zero
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.

29
The categories of this paper are: funct-an
5
The categories of this paper are: gr-qc
20
The categories of this paper are: acc-phys
31
The categories of this paper are: ao-sci
28
The categories of this paper are: alg-geom
11
The categories of this paper are: hep-lat
37
The categories of this paper are: supr-con
15
The categories of this paper are: nucl-ex
0
The categories of this paper are: hep-ph
34
The categories of this paper are: chem-ph
27
The categories of this paper are: comp-gas
32
The categories of this paper are: atom-ph
21
The categories of this paper are: adap-org
17
The categories of this paper are: q-fin
2
The categories of this paper are: math
7
The categories of this paper are: hep-th