CS Paper Radar

Connections Between Quadratic Transform for Fractional Programming and Schur Complement

Kaiming Shen, Kareem M. Attiah, Yannan Chen, Wei Yu

cs.IT ·submitted 2026-09-18 13:06 UTC · v1
published

Abstract

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.

Comment
11 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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.63
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

Normalized Cuts and Data Clustering via Matrix Fractional Programming

cs.LG eess.SP ·2026-10-27 ·Yannan Chen, Beichen Huang, Licheng Zhao, Chris Ding, Kaiming Shen
top venue similarity 0.61
Abstract · 15 pages, 15 figures

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.

0.42

Beamforming and Filter Design for Bistatic ISAC under Known and Unknown Transmit Symbols

eess.SP ·2026-08-17 ·Mohammad Hatami, Nhan Thanh Nguyen, Markku Juntti
publishedbenchmark similarity 0.54
Abstract · 5 pages, 3 figures. Accepted for presentation at the IEEE SPAWC 2026 conference

This paper investigates the joint design of beamforming and radar receive filters in a multiuser bistatic integrated sensing and communications (ISAC) system, aiming to maximize the minimum radar signal-to-interference-plus-noise ratio (SINR) under communications SINR and transmit power constraints. We consider two scenarios: transmitted signals are either known or unknown at the radar receiver. We develop tractable solutions to the resulting non-convex optimization problems in both cases. For the known-signal case, we derive closed-form radar receive filters and iteratively design beamforming using fractional programming (FP) and successive convex approximation (SCA). For the unknown case, we adopt an alternating optimization (AO) approach to jointly design the beamforming and receive filters. Numerical results demonstrate that, while both approaches achieve comparable performance under per-slot optimization, knowledge of the transmitted symbols provides significant gains in multi-slot processing via coherent integration. Moreover, the proposed ISAC designs perform close to the radar-only benchmark under moderate communication requirements.

0.57

The Interference-Conjugate Transform: The Tightest Interference-Linear Surrogate for Power Control, Scheduling and Beamforming in Wireless Networks

cs.IT eess.SP ·2026-10-27 ·Ahmad Khan
benchmarktheory similarity 0.52
Abstract

Closed-form fractional programming (FP), weighted MMSE (WMMSE), and the 2026 surrogate-enhanced methods SEFP and XMMSE all maximize the weighted sum rate by iteratively maximizing a surrogate linear in the interference power. We show that this family admits a unique best member: the interference-conjugate transform (ICT), which replaces each rate term $\log(1+a/b)$ by $\max_{κ\ge0}[Ω(κa)-κb]$, where $Ω$ is the closed-form partial convex conjugate of the rate in the interference variable and the optimal multiplier is the interference price $a/(b(a+b))$. We prove that, for any fixed price, $Ω(κ\,\cdot)$ is the pointwise largest own-signal function compatible with a valid interference-linear lower bound, and that tightness at an anchor forces the price. Hence all four benchmark surrogates, which share this price and differ only in their own-signal term, are dominated pointwise by ICT. At SINR $γ$, the benchmarks' own-signal curvature exceeds the true curvature by factors behaving as $γ/2$ (FP/WMMSE) and $(\logγ)/2$ (SEFP/XMMSE), against $1+1/(γ(γ+2))$ for ICT, and this ordering carries over to the certified ascent per iteration and the asymptotic linear convergence rate. ICT yields closed-form updates at the benchmarks' per-iteration cost for single-antenna power control, uplink joint scheduling and power control, and multi-cell MISO beamforming, and the first solver-free algorithm for sum-least-$q$th-percentile rate maximization, via a $K$-dimensional convex dual with closed-form gradient and Hessian and a certified duality gap. In uplink scheduling, ICT improves proportional-fairness utility over FP by +7.03 and over SEFP by +3.35 (60/60 drops) using 18.7 iterations per slot vs. 49.7 and 38.0; in MISO beamforming with $M=8$, it reaches 99.9% of its final value in a median of 9 iterations vs. 16 (XMMSE) and 1160 (FP/WMMSE).

0.11

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

cs.LG math.NAmath.OC ·2026-08-28 ·Matthew McCarver, Jing Qin
similarity 0.52
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

Convex Reformulation of Minkowski-Sum Outer Approximation for Matrix Ellipsoids in Data-Driven Control

eess.SY math.OC ·2026-11-02 ·Taira Kaminaga, Hampei Sasahara
similarity 0.52
Abstract · 8 pages, 6 figures

Approximating Minkowski sums of matrix ellipsoids by a single matrix ellipsoid provides a tractable description of noise bounds for controller design from noisy data. Existing linear matrix inequality (LMI) conditions can be used to compute such approximations, but directly solving the resulting optimization problems can be computationally expensive. This paper develops an efficient method for finding a minimum-volume outer matrix ellipsoid under these LMI conditions. Although the corresponding problem for ordinary vector-valued ellipsoids is convex, the objective function in the matrix-valued case is nonconvex. We find that the problem admits an equivalent convex reformulation, which resolves this difficulty. We first eliminate the matrix variables using equivalent LMI transformations and objective monotonicity, leaving one positive scalar variable per matrix ellipsoid in the sum. We then show that the objective becomes convex after a logarithmic change of variables. The resulting problem contains neither LMI constraints nor matrix variables and can therefore be solved efficiently. Numerical experiments confirm that the proposed method is substantially faster than the LMI-based method. An application to data-driven control further illustrates the tradeoff between guaranteed control performance and computation time.

0.35

A Duality Reformulation of the Companion-Matrix Lyapunov Problem

eess.SY math.OC ·2026-09-11 ·Augusto Ferrante
theory similarity 0.51
Abstract

We study the relation between positive semidefiniteness and entrywise nonnegativity for solutions of continuous-time Lyapunov equations. For a real Hurwitz matrix $A$, we show that the solution of $AP+PA^\top=-Q$ is positive semidefinite for every symmetric entrywise nonnegative $Q$ if and only if the solution of $A^\top X+XA=-R$ is entrywise nonnegative for every positive semidefinite $R$. This equivalence follows from the adjointness of the two solution operators and extends to all real unmixed matrices. We then prove that both properties hold for every real Hurwitz companion matrix, settling a conjecture previously established under the additional assumption of a real spectrum. The proof combines a controllability-Gramian normalization with a pairwise positivity theorem for the coefficients of the adjugate polynomial of a real accretive matrix. The latter is obtained from a coefficient-sign property of bivariate polynomials, an auxiliary determinant that does not vanish on the product of two open right half-planes, and a rank-one perturbation argument. Covariance and energy interpretations connect these results with dissipative realizations, damped second-order systems, and comparisons between input Gramians.

0.33

Minimizing Monotone Norms in Fractional Load Balancing

cs.DS math.OC ·2026-11-11 ·Daniel Blankenburg, Antonia Ellerbrock, Thomas Kesselheim, Jens Vygen
similarity 0.51
Abstract · 44 pages, 2 figures

We devise a fully polynomial time approximation scheme for minimizing a monotone norm $\left\lVert\cdot\right\rVert$ over a convex set $X\subseteq \mathbb{R}^d_{\geq 0}$. We study the multi-customer setting, where $X=\sum_{i=1}^n X_i$ and the solution set $X_i\subseteq \mathbb{R}^d_{\geq 0}$ is given by a linear minimization oracle for each customer $i$. Our algorithm computes, for any given $\varepsilon>0$, a $(1+\varepsilon)$-approximate solution. With high probability, it uses $\tilde{\mathcal{O}}\left( \varepsilon^{-2}(n+d) \right)$ single-customer linear minimization oracle calls and the same number of generalized KL projections to the dual space $Y=\{y\in \mathbb{R}^d_{\geq 0}: \left\lVert y \right\rVert^* \le 1\}$. We assume no prior knowledge on $X$, and our running time depends only on $n$, $d$, and $\varepsilon$. Our result is robust in the sense that it allows for approximate linear minimization oracles and approximate KL projections. We show that the (approximate) KL projection can be performed efficiently for large classes of monotone norms, demonstrating the applicability of our approach. While such a result (with exact projection) is well-known for the $\ell_{\infty}$ norm via multiplicative weight updates and was recently obtained for ordered norms via a smooth norm approximation and a novel randomization, existing techniques do not extend to general monotone norms. In particular, a key feature used in previous proofs was dual price stability, which was derived from a global contraction property of the KL projection to the dual space $Y$. We show that this property does not extend to general monotone norms. Therefore, we use a different price mechanism, based on the well-known mirror descent paradigm, for which a local contraction property holds and guarantees stability.

0.37