CS Paper Radar

Normalized Cuts and Data Clustering via Matrix Fractional Programming

Yannan Chen, Beichen Huang, Licheng Zhao, Chris Ding, Kaiming Shen

cs.LG eess.SP ·submitted 2026-10-27 04:20 UTC · v1
top venue

Abstract

The normalized cut (NCut) problem is a fundamental one in the area of data clustering. Despite its fractional structure, the NCut problem is seldom considered from a fractional programming (FP) perspective in the existing literature. The main reason is that the conventional FP method is inadequate for this problem case: the classical Dinkelbach's transform can only handle a single ratio and hence is limited to the two-class clustering, whereas the multi-class clustering involves multiple ratio terms. This work proposes a novel so-called multidimensional quadratic transform that is capable of dealing with the multi-ratio case; it recasts the NCut problem into a bipartite matching problem---which can be immediately solved by linear search. Furthermore, we explore the connection between the proposed FP method and the minorization-maximization (MM) theory, and in turn characterize the convergence behavior of our algorithm. Finally, we conduct experiments to numerically demonstrate the advantages of the proposed FP-based algorithm in a variety of data clustering and image segmentation tasks.

Comment
15 pages, 15 figures
DOI
10.1109/TMC.2026.3748126

Closest papers

Nearest neighbours by meaning across the whole index.

Connections Between Quadratic Transform for Fractional Programming and Schur Complement

cs.IT ·2026-09-18 ·Kaiming Shen, Kareem M. Attiah, Yannan Chen, Wei Yu
published similarity 0.61
Abstract · 11 pages

This paper shows that there are intimate connections between the quadratic transform technique for solving fractional programming (FP) problems and the Schur-complement technique in matrix analysis. We demonstrate that the quadratic transform technique is related to two aspects of the Schur complement: (i) the linear matrix inequality (LMI) condition for positive semidefiniteness and (ii) the matrix determinant formula. Specifically, we establish that the quadratic transform and the Schur-complement LMI condition imply each other. This connection allows us to provide new interpretations of the auxiliary variable in the quadratic transform, and it allows us to rederive the Schur-complement determinant formula. Furthermore, this connection leads to generalizations of the quadratic transform in FP and the Schur-complement LMI that can accommodate generalized matrix inverse. As an application in information theory, we apply the generalized FP framework to the least-favorable-noise minimax formulation of the Gaussian vector broadcast channel sum capacity problem. When the least-favorable noise covariance is singular, matrix-inverse-based Karush-Kuhn-Tucker (KKT) analysis would require a careful analysis of the input and output spaces of the channel. We show using generalized FP that an auxiliary-variable representation of the singular matrix fraction directly yields the reciprocal multiple-access channel and recovers the uplink-downlink duality relation for sum capacity.

0.41

Separable Nonnegative Matrix Factorization Using Powered Ratio-of-Norms Regularization

cs.LG math.NAmath.OC ·2026-08-28 ·Matthew McCarver, Jing Qin
similarity 0.57
Abstract

Separable nonnegative matrix factorization (SNMF) has been widely used for low-rank representation and clustering of nonnegative data, owing to its ability to produce part-based and interpretable decompositions. In particular, SNMF is closely related to graph clustering and community detection. To enhance sparsity and identifiability of the learned factors, we propose an $\ell_1^p/\ell_2$-regularized SNMF model based on a powered ratio-of-norms regularizer. The resulting formulation is nonconvex and nonsmooth, which poses significant challenges for optimization. To address this, we develop efficient algorithms based on the difference-of-convex function algorithm (DCA) and the alternating direction method of multipliers (ADMM). The proposed methods decompose the original problem into tractable subproblems, leveraging closed-form proximal operators associated with the powered norm terms. We establish descent and limiting criticality properties for the DCA scheme and convergence under standard assumptions for the ADMM scheme. Extensive numerical experiments on synthetic datasets and hand gesture classification tasks demonstrate that the proposed approach achieves competitive or improved performance in anchor identification and classification accuracy compared with existing SNMF methods, while maintaining competitive computational efficiency.

0.21

GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization

cs.LG cs.ARcs.PF ·2026-09-28 ·Peng Xu, Nihar Koganti, Volodymyr Kindratenko, Xiaohui Chen
similarity 0.53
Abstract

Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for $K$-means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.

0.28

LoomSC: Scalable Deep Subspace Clustering with Projector Factorization and Exact Spectral Reduction

cs.CV cs.AI ·2026-10-07 ·Nairouz Mrabah, Youssef Melki, Mohamed Bouguessa, Riadh Ksantini, Shakeeb Murtaza +1 more
similarity 0.51
Abstract · 19 pages, 7 figures, 5 tables; includes appendices

Dense self-expression matrices and full-affinity spectral clustering limit the scalability of subspace clustering. We introduce the Latent Orthogonal Optimization Model for Subspace Clustering (LoomSC), a framework that addresses both bottlenecks through projector factorization and exact spectral reduction. Motivated by the spectral structure of least-squares regression, LoomSC jointly learns latent features and a projector self-representation through two thin factors. Alternating Procrustes and least-squares updates preserve the sample factor's orthogonality while keeping the coefficient matrix implicit. We construct a nonnegative quadratic affinity that preserves the projector's support. An exact feature map then reduces its normalized spectral problem to an eigenproblem whose dimension depends only on the factor width. Neither the full affinity nor the sample Laplacian needs to be formed. Our analysis quantifies the projector approximation and identifies conditions for subspace preservation and within-subspace connectivity. For fixed dimensions and iteration budgets, the complete pipeline has linear time and memory complexity in the number of samples. Across five image-clustering benchmarks, LoomSC ranks first or second in all 15 dataset-metric comparisons against 9 state-of-the-art baselines. Its mean accuracy exceeds the highest baseline mean by 6.66 percentage points. Synthetic experiments scale to 500,000 samples while maintaining at least 99.8% accuracy.

0.24

Horospherically convex optimization for fractional subspace packing and its applications

cs.DS ·2026-08-14 ·Hiroshi Hirai
similarity 0.51
Abstract

In this paper, we address a semi-infinite LP relaxation of the vector-subspace packing problem. This is a higher-dimensional generalization of the fractional linear matroid parity problem and is closely related to Brascamp-Lieb polytopes. We show that the dual of this LP can be formulated as ``linear programming on a Euclidean building," namely, the problem of minimizing a Busemann function over an intersection of horoballs. This provides a natural example of horospherically convex optimization, recently introduced by Goodwin et al. (2026) and Criscitiello and Kim (2025). By applying the incremental Busemann subgradient method, we obtain an additive FPTAS for the problem. As applications, we obtain a new and simpler polynomial-time algorithm for fractional linear matroid parity, and new algorithms for the membership problem of Brascamp-Lieb polytopes.

0.32

A $(3+ε)$-Approximation for Fair $k$-Means and a Matching Lower Bound

cs.CG cs.LG ·2026-09-07 ·Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding
theory similarity 0.50
Abstract

Fair clustering aims to prevent algorithmic bias against protected groups. We study Euclidean fair $k$-means, in which the proportion of each protected group in every cluster lies between prescribed lower and upper bounds. Because these constraints violate the nearest-center assignment property, center selection is coupled with point assignment. We introduce the drift-regularized relaxation, a new convex relaxation solved by a modified Frank-Wolfe method with linear-programming iterations, whose optimality condition controls the cost of converting its solution into $k$ fair clusters. Combined with any $ρ$-approximation algorithm for weighted $k$-means, the relaxation yields an exactly fair fractional solution of cost at most $2ρ+1+ε$ times the fractional optimum, improving the previous ratio $1+4ρ+ε$. In fixed dimension, this improves the best known ratio from $5+O(ε)$ to $3+O(ε)$. The fractional solution can be rounded to an integral one without changing the centers or increasing the cost, at a bounded additive violation of the fairness bounds. We also show that a $(3-δ)$-approximation is NP-hard for every fixed $δ>0$, even on the line with fractional assignments, so $3$ is the exact approximation threshold for fractional fair $k$-means in fixed dimension. The same guarantees hold for $k$-sparse Wasserstein barycenters, a special case of fractional fair $k$-means. More generally, they hold whenever every cluster must satisfy given homogeneous linear inequalities in the fractions of its points, such as a bound on the ratio between two groups or on the average of a numerical attribute in every cluster.

0.09

Surrogate-Enhanced Fractional Programming for MIMO Device-to-Device Interference Networks

cs.IT eess.SP ·2026-09-29 ·Zihan Jiao, Xinping Yi, Shi Jin, Giuseppe Caire
similarity 0.50
Abstract · Corrected a typo in the abstract metadata; manuscript unchanged

Interference management in multi-stream multi-input multi-output (MIMO) device-to-device (D2D) networks often leads to weighted sum-rate maximization with sum-log-determinant involving matrix-valued signal-to-interference-plus-noise ratios (SINRs). The state-of-the-art paradigms, including weighted minimum mean-square error (WMMSE) and fractional programming (FP), have achieved tremendous success in link scheduling, power control, and beamforming problems. Recently, an upgraded FP approach, named surrogate-enhanced FP (SEFP) in a scalar form, has attained improved performance in joint uplink scheduling and power control in coordinated multicell SISO networks. The proposed SEFP improves the surrogate construction of the classical Lagrangian dual transform plus quadratic transform for logarithmic fractional objectives with a novel reciprocal-inverse transform (RIT), yet its extension to the matrix form for MIMO settings does not seem straightforward because the matrix ratio and the auxiliary matrix generally do not commute. In this paper, by leveraging mathematical tools from Hermitian functional calculus, we extend RIT to matrix ratios by lifting the scalar RIT along the eigendirections of an auxiliary matrix and recasting the resulting directional construction in an operator form. Following, we develop a matrix SEFP framework for weighted sum-log-determinant maximization. Further, we establish a unified view of SEFP and the recently proposed XMMSE method, specify when the two algorithms attribute to identical minorization-maximization (MM) surrogates and variable update trajectories, and prove XMMSE can be considered as a special case of SEFP under the algorithmic family perspective. Inspired by the unified view, we develop SEFPLinQ for the joint scheduling and beamforming optimization in flexible-association MIMO D2D networks. Numerical results demonstrate consistent performance gains.

0.22

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

cs.DS cs.CG ·2026-10-28 ·Asaf Dallal, Robert Krauthgamer
similarity 0.50
Abstract

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\logΔ))$ suffices for Euclidean inputs of aspect ratio at most $Δ$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

0.18