  We consider a class of structured fractional minimization problems, in which
the numerator part of the objective is the sum of a differentiable convex
function and a convex non-smooth function, while the denominator part is a
convex or concave function. This problem is difficult to solve since it is
non-convex. By exploiting the structure of the problem, we propose two
Coordinate Descent (CD) methods for solving this problem. The proposed methods
iteratively solve a one-dimensional subproblem \textit{globally}, and they are
guaranteed to converge to coordinate-wise stationary points. In the case of a
convex denominator, under a weak \textit{locally bounded non-convexity
condition}, we prove that the optimality of coordinate-wise stationary point is
stronger than that of the standard critical point and directional point. Under
additional suitable conditions, CD methods converge Q-linearly to
coordinate-wise stationary points. In the case of a concave denominator, we
show that any critical point is a global minimum, and CD methods converge to
the global minimum with a sublinear convergence rate. We demonstrate the
applicability of the proposed methods to some machine learning and signal
processing models. Our experiments on real-world data have shown that our
method significantly and consistently outperforms existing methods in terms of
accuracy.
