  Faster-than-Nyquist (FTN) signaling is a promising non-orthogonal physical
layer transmission technique to improve the spectral efficiency of future
communication systems but at the expense of intersymbol-interference (ISI). In
this paper, we investigate the detection problem of FTN signaling and formulate
the sequence estimation problem of any $M$-ary phase shift keying (PSK) FTN
signaling as an optimization problem that turns out to be non-convex and
nondeterministic polynomial time (NP)-hard to solve. We propose a novel
algorithm, based on concepts from semidefinite relaxation (SDR) and Gaussian
randomization, to detect any $M$-ary PSK FTN signaling in polynomial time
complexity regardless of the constellation size $M$ or the ISI length.
Simulation results show that the proposed algorithm strikes a balance between
the achieved performance and the computational complexity. Additionally,
results show the merits of the proposed algorithm in improving the spectral
efficiency when compared to Nyquist signaling and the state-of-the-art schemes
from the literature. In particular, when compared to Nyquist signaling at the
same error rate and signal-to-noise ratio, our scheme provides around $17\%$
increase in the spectral efficiency at a roll-off factor of 0.3.
