Slides: Fractional Programming for Discrete Optimization in Signal Processing and Machine Learning

Fractional programming (FP) refers to optimization problems involving functions of ratios. FP plays an important role in signal processing and machine learning, because many problems in these application areas are fractionally structured. This talk focuses on a state-of-the-art FP method called the quadratic transform and illustrates the use of quadratic transform for discrete optimization problems through two application examples. The first example is the joint optimization of beamforming and user scheduling for uplink wireless cellular networks, which is a mixed discrete and continuous nonlinear optimization problem. In this domain, the weighted minimum mean square error (WMMSE) algorithm has been extensively used. We connect WMMSE to FP, and further improve upon WMMSE by using the quadratic transform. The second example is the 0-1 normalized-cut (NCut) problem for data clustering and image segmentation. Unlike the previous relaxation-based methods, the proposed FP method recasts the NCut problem into a sequence of weighted bipartite matching problems, which can be solved efficiently without relaxing the discrete variables.