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

Valentine Olanubi; Phineas Agar; Brendan Ames

math.OCJan 7, 2026

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

Authors: Valentine Olanubi, Phineas Agar, Brendan Ames

Organizations: University of Alabama, Department of Mathematics · Department of Mathematics, University of Alabama, Tuscaloosa, AL, USA · University of Southampton, School of Mathematical Sciences · School of Mathematical Sciences, University of Southampton, Southampton, UK

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.

Explore similar work

Sep 15, 2026math.NA

Near-Optimal Nonconvex Matrix Completion

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an

n\times n

matrix of rank

r

with incoherence parameter

μ

and condition number

κ

, the two methods achieve exact recovery with high probability from

O(μnr\log n\log(nκ))

and

O(μnr\log n\log(2μrκ))

observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Jian-Feng Cai, Xiliang Lu, Juntao You

Tensor Completion Optimal Sample Complexity

Ask PDF

Jul 24, 2026stat.ML

Graph-Based Correlation Matrix Generation: A Convex Optimization Approach

This work addresses the generation of theoretical correlation matrices with prescribed sparsity patterns associated to graph structures. We propose a novel convex optimization framework in which an initial matrix is projected onto an elliptope under a positive semidefiniteness constraint. Several numerical schemes are implemented and compared. The problem falls within the broader class of matrix completion, where off-diagonal entries corresponding to absent edges are fixed to zero and diagonal entries are fixed to one. Beyond this structural constraint, the approach offers greater flexibility than existing methods by allowing control over the mean of the off-diagonal entry distribution, enabling the generation of correlation matrices that better reflect realistic data. This procedure is not designed to yield a uniform distribution over the feasible set; rather, it provides a principled and tunable way to construct correlation matrices suitable for benchmarking statistical methods for graphical model inference. Theoretical guarantees on the existence of solutions are established, both in the general setting and under the additional mean constraint. Simulation studies illustrate the properties of the generated matrices with respect to graph structure. The methodology is applied to two real-world datasets from neuroscience and finance, and a comparison with GAN-based correlation matrix generation is provided.

Ali Fakhar, K{é}vin Polisano, Ir{è}ne Gannaz +1

Tensor Completion Exponential Random Graph Models Covariance Estimation Sparsity Convex Optimization

Ask PDF

Oct 28, 2025cs.IT

Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on

\mathbf{A}

(e.g., restricted isometry property) guaranteeing unique recovery of

\mathbf{x}^\star

from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

with

\|\mathbf{e}\|_0 \leq q

. However, these guarantees provide no guidance once exact recovery fails. This limitation obscures simple robustness phenomena -- for instance, repeated rows in

\mathbf{A}

can preserve nontrivial information about

\mathbf{x}^\star

under sparse corruption. In this paper, we study what information about

\mathbf{x}^\star

can be \emph{uniformly} recovered from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

for arbitrary

\mathbf{A}\in\mathbb{R}^{m\times n}

and \emph{any}

q

-sparse

\mathbf{e}

. We show that the robust information is precisely

\mathbf{x}^\star + \ker(\mathbf{U})

, where

\mathbf{U}

is the orthogonal projection onto the intersection of rowspaces of all submatrices of

\mathbf{A}

obtained by deleting

2q

rows. This clarifies how the row structure of

\mathbf{A}

governs whether a

q

-sparse corruption allows exact, partial, or only trivial recovery. We further prove every

\mathbf{x}

minimizing

\|\mathbf{y} - \mathbf{A} \mathbf{x}\|_0

belongs to

\mathbf{x}^\star + \ker(\mathbf{U})

, yielding a constructive approach to recover this set. For i.i.d. Gaussian matrices, we establish a sharp phase transition between exact and trivial recovery. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT.

Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1

Sparse Observations Adversarial Corruption 3D Gaussian Splatting Computed Tomography

Ask PDF