Fractional programming (FP) arises in various communications and signal processing problems because several key quantities in the field are fractionally structured, e.g., the Cramér-Rao bound, the Fisher information, and the signal-to-interference-plus-noise ratio (SINR). A recently proposed method called the quadratic transform has been applied to the FP problems extensively. The main contributions of the present paper are two-fold. First, we investigate how fast the quadratic transform converges. To the best of our knowledge, this is the first work that analyzes the convergence rate for the quadratic transform as well as its special case the weighted minimum mean square error (WMMSE) algorithm. Second, we accelerate the existing quadratic transform via a novel use of Nesterov's extrapolation scheme [2]. Specifically, by generalizing the minorization-maximization (MM) approach in [3], we establish a nontrivial connection between the quadratic transform and the gradient projection, thereby further incorporating the gradient extrapolation into the quadratic transform to make it converge more rapidly. Moreover, the paper showcases the practical use of the accelerated quadratic transform with two frontier wireless applications: integrated sensing and communication (ISAC) and massive multiple-input multiple-output (MIMO).

The Normalized cut (NCut) problem is a fundamental and yet notoriously difficult one in the unsupervised clustering field. Because the NCut problem is fractionally structured, the fractional programming (FP) based approach has worked its way into a new frontier. However, the conventional FP techniques are insufficient: the classic Dinkelbach's transform can only deal with a single ratio and hence is limited to the two-class clustering, while the state-of-the-art quadratic transform accounts for multiple ratios but fails to convert the NCut problem to a tractable form. This work advocates a novel extension of the quadratic transform to the multidimensional ratio case, thereby recasting the fractional 0-1 NCut problem into a bipartite matching problem---which can be readily solved in an iterative manner. Furthermore, we explore the connection between the proposed multidimensional FP method and the minorization-maximization theory to verify the convergence.

Fractional programming (FP) arises in various communications and signal processing problems because several key quantities in these fields are fractionally structured, e.g., the Cramér-Rao bound, the Fisher information, and the signal-to-interference-plus-noise ratio (SINR). A recently proposed method called the quadratic transform has been applied to the FP problems extensively. The main contributions of the present paper are two-fold. First, we investigate how fast the quadratic transform converges. To the best of our knowledge, this is the first work that analyzes the convergence rate for the quadratic transform as well as its special case the weighted minimum mean square error (WMMSE) algorithm. Second, we accelerate the existing quadratic transform via a novel use of Nesterov’s extrapolation scheme. Specifically, by generalizing the minorization-maximization (MM) approach, we establish a subtle connection between the quadratic transform and the gradient projection, thereby further incorporating the gradient extrapolation into the quadratic transform to make it converge more rapidly. Moreover, the paper showcases the practical use of the accelerated quadratic transform with two frontier wireless applications: integrated sensing and communications (ISAC) and massive multiple-input multiple-output (MIMO).

A major challenge with the multi-ratio Fractional Program (FP) is that the existing methods for the maximization problem typically do not work for the minimization case. We propose a novel technique called inverse quadratic transform for the sum-of-ratios minimization problem. Its main idea is to reformulate the min-FP problem in a form amenable to efficient iterative optimization. Furthermore, this transform can be readily extended to a general cost-function-of-multiple-ratios minimization problem. We also give a Majorization-Minimization (MM) interpretation of the inverse quadratic transform, showing that all those desirable properties of MM can be carried over to the new technique. Moreover, we demonstrate the application of inverse quadratic transform in minimizing the Age-of-Information (AoI) of data networks.

In this paper, we consider the perfect demand matching problem ( PDM ) which combines aspects of the knapsack problem along with the b -matching problem. It is a generalization of the maximum weight matching problem which has been fundamental in the development of theory of computer science and operations research . This problem is NP-hard and there exists a constant ϵ > 0 such that the problem admits no 1 + ϵ -approximation algorithm, unless P=NP. Here, we investigate the performance of a distributed message passing algorithm called Max-sum belief propagation for computing the problem of finding the optimal perfect demand matching. As the main result, we demonstrate the rigorous theoretical analysis of the Max-sum BP algorithm for PDM , and establish that within pseudo-polynomial-time, our algorithm could converge to the optimal solution of PDM , provided that the optimal solution of its LP relaxation is unique and integral. Different from the techniques used in previous literature, our analysis is based on primal-dual complementary slackness conditions , and thus the number of iterations of the algorithm is independent of the structure of the given graph. Moreover, to the best of our knowledge, this is one of a very few instances where BP algorithm is proved correct for NP-hard problems.

In this paper, we consider the multiclass clustering problem involving a hypergraph model. Fundamentally, we study a new normalized Laplacian tensor of an even-uniform weighted hypergraph. The hypergraph's connectivity is related with the second smallest Z-eigenvalue of the proposed Laplacian tensor. Particularly, an analogue of fractional Cheeger inequality holds. Next, we generalize the Laplacian tensor based approach from biclustering to multiclass clustering. A tensor optimization model with an orthogonal constraint is established and analyzed. Finally, we apply our hypergraph clustering approach to image segmentation and motion segmentation problems. Experimental results demonstrate that our method is effective.

This paper further explores bathymetric extraction techniques using overlapping orthoimages in shallow water areas through two-medium ray refraction and multispectral information inversion. In texture-rich areas, a ray refraction method using overlapping orthoimages is developed to calculate the depth information of the underwater features. In texture-less areas, the commonly-used multispectral inversion techniques are applied. The depth information from the ray refraction method acts as the references for the multispectral inversion techniques, therefore, an integrated approach of extracting the shallow bathymetry based on overlapping orthoimages is formed. The results from an aerial overlapping orthoimages experiment show that 0.5 m accuracy can be achieved in the study area. The proposed approach is the combination of two simple methods, and is easy to be implemented and flexible to use, giving that there are a large amount of existing overlapping multispectral orthoimages in water related areas, the proposed approach has the great potentials for the practical use.

In diffusion-weighted magnetic resonance imaging, the estimation of the orientations of multiple nerve fibers in each voxel (the fiber orientation distribution (FOD)) is a critical issue for exploring the connection of cerebral tissue. In this paper, we establish a convex semidefinite programming (CSDP) model for the FOD estimation. One feature of the new model is that it can ensure the statistical meaning of FOD since as a probability density function, FOD must be nonnegative and have a unit mass. To construct such a statistically meaningful FOD, we consider its approximation by a sum of squares (SOS) polynomial and impose the unit-mass by a linear constraint. Another feature of the new model is that it introduces a new regularization based on the sparsity of nerve fibers. Due to the sparsity of the orientations of nerve fibers in cerebral white matter, a heuristic regularization is raised, which is inspired by the Z-eigenvalue of a symmetric tensor that closely relates to the SOS polynomial. To solve the CSDP efficiently, we propose a new Peaceman--Rachford splitting method and prove its global convergence. Numerical experiments on synthetic and real-world human brain data show that, when compared with some existing approaches for fiber estimations, the new method gives a sharp and smooth FOD. Further, the proposed Peaceman--Rachford splitting method is shown to have good numerical performances comparing several existing methods.

The positive definiteness of a diffusion tensor is important in magnetic resonance imaging because it reflects the phenomenon of water molecular diffusion in complicated biological tissue environments. To preserve this property, we represent it as an explicit positive semidefinite (PSD) matrix constraint and some linear matrix equalities. The objective function is the regularized linear least squares fitting for the log-linearized Stejskal--Tanner equation. The regularization term is the heuristic nuclear norm of the PSD matrix, since we expect it to be of low rank. In this way, we establish a convex quadratic semidefinite programming (SDP) model, whose global solution exists. The optimal solution could be solved by three efficient methods. While there are two state-of-the-art solvers---SDPT3 and QSDP---for the primal problem, we design a new augmented Lagrangian based alternating direction method (ADM) for the dual problem. Sensitivity analyses on the coefficients of the optimal diffusion tensor and the optimal objective function value with respect to noise-corrupted signals are presented. Experiments on synthetic data with multiple fibers show that the new method is robust to the Rician noise and outperforms several existing methods. Furthermore, when the fiber orientation distribution function is considered, the new method is competitive with the Q-ball imaging. Using the human brain data, we illustrate that the new method could capture the crossing of three nervous fiber bundles. Additionally, the new method generates positive definite generalized diffusion tensors in all voxels, while the unconstrained least squares fitting fails. Finally, we confirm that the ADM solver is more efficient than SDPT3 and QSDP for this special problem.

Abstract:Using a conjugate gradient method, a novel iterative support vector machine (FISVM) is proposed, which is capable of generating a new non‐linear classifier. We attempt to solve a modified primal problem of proximal support vector machine (PSVM) and show that the solution of the modified primal problem reduces to solving just a system of linear equations as opposed to a quadratic programming problem in SVM. This algorithm not only has no requirement for special optimization solvers, such as linear or quadratic programming tools, but also guarantees fast convergence. The full algorithm merely needs four lines of MATLAB codes, which gives results that are similar to or better than that of several new learning algorithms, in terms of classification accuracy. Besides, the proposed stand‐alone approach is capable of dealing with instability of classification performance of smooth support vector machine, generalized proximal support vector machine, PSVM and reduced support vector machine. Experiments carried out on UCI datasets show the effectiveness of our approach.