  In this paper we develop efficient first-order algorithms for the generalized
trust-region subproblem (GTRS), which has applications in signal processing,
compressed sensing, and engineering. Although the GTRS, as stated, is nonlinear
and nonconvex, it is well-known that objective value exactness holds for its
SDP relaxation under a Slater condition. While polynomial-time SDP-based
algorithms exist for the GTRS, their relatively large computational complexity
has motivated and spurred the development of custom approaches for solving the
GTRS. In particular, recent work in this direction has developed first-order
methods for the GTRS whose running times are linear in the sparsity (the number
of nonzero entries) of the input data. In contrast to these algorithms, in this
paper we develop algorithms for computing $\epsilon$-approximate solutions to
the GTRS whose running times are linear in both the input sparsity and the
precision $\log(1/\epsilon)$ whenever a regularity parameter is positive. We
complement our theoretical guarantees with numerical experiments comparing our
approach against algorithms from the literature. Our numerical experiments
highlight that our new algorithms significantly outperform prior
state-of-the-art algorithms on sparse large-scale instances.
