Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming

• URL: http://arxiv.org/abs/2601.03946v1
• Date: Wed, 07 Jan 2026 14:02:25 GMT
• Title: Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming
• Abstract summary: We consider the densest submatrix problem, which seeks the submatrix of fixed size of a given binary matrix that contains the most nonzero entries.<n>Much recent research has focused on the development of sufficient conditions for exact solution of the densest submatrix problem.<n>We extend these results to the more realistic setting where the input matrix may contain emphmany large dense subgraphs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the densest submatrix problem, which seeks the submatrix of fixed size of a given binary matrix that contains the most nonzero entries. This problem is a natural generalization of fundamental problems in combinatorial optimization, e.g., the densest subgraph, maximum clique, and maximum edge biclique problems, and has wide application the study of complex networks. Much recent research has focused on the development of sufficient conditions for exact solution of the densest submatrix problem via convex relaxation. The vast majority of these sufficient conditions establish identification of the densest submatrix within a graph containing exactly one large dense submatrix hidden by noise. The assumptions of these underlying models are not observed in real-world networks, where the data may correspond to a matrix containing many dense submatrices of varying sizes. We extend and generalize these results to the more realistic setting where the input matrix may contain \emph{many} large dense subgraphs. Specifically, we establish sufficient conditions under which we can expect to solve the densest submatrix problem in polynomial time for random input matrices sampled from a generalization of the stochastic block model. Moreover, we also provide sufficient conditions for perfect recovery under a deterministic adversarial. Numerical experiments involving randomly generated problem instances and real-world collaboration and communication networks are used empirically to verify the theoretical phase-transitions to perfect recovery given by these sufficient conditions.

Related papers

• Solving Minimal Problems Without Matrix Inversion Using FFT-Based Interpolation [8.359861060031223]
  We propose a sampling-based, inversion-free method that constructs solvers using sparse hidden-variables.<n>The proposed solver achieves strong numerical stability and competitive stability, particularly for small-scale problems.
  arXiv  Detail & Related papers  (2026-05-07T17:03:56Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• The Structural Complexity of Matrix-Vector Multiplication [0.10485739694839669]
  We show that the matrix-vector multiplication problem can be solved with $tildeO(n2)$ preprocessing and $tilde O(n2-1/d)$ query time.<n>Our results yield the first non-trivial upper bounds for many applications.
  arXiv  Detail & Related papers  (2025-02-28T17:11:36Z)
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling [10.824999179337558]
  We show that it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities.
  arXiv  Detail & Related papers  (2024-02-29T23:24:43Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Learning a Compressive Sensing Matrix with Structural Constraints via Maximum Mean Discrepancy Optimization [17.104994036477308]
  We introduce a learning-based algorithm to obtain a measurement matrix for compressive sensing related recovery problems. Recent success of such metrics in neural network related topics motivate a solution of the problem based on machine learning.
  arXiv  Detail & Related papers  (2021-10-14T08:35:54Z)
• Identifiability in Exact Two-Layer Sparse Matrix Factorization [0.0]
  Sparse matrix factorization is the problem of approximating a matrix Z by a product of L sparse factors X(L) X(L--1). This paper focuses on identifiability issues that appear in this problem, in view of better understanding under which sparsity constraints the problem is well-posed.
  arXiv  Detail & Related papers  (2021-10-04T07:56:37Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices [0.0]
  Singular Value Decomposition (SVD) is a well studied research topic in many fields and applications. We propose Ranky, set of methods to solve rank problem on large and sparse matrices in a distributed manner.
  arXiv  Detail & Related papers  (2020-09-21T11:36:28Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.