Detection of lines in a point cloud
It really depends, how will you measure the quality of the solutions? what are your requirements, real time, high accuracy? how large is the point cloud?

You mentioned valid, yet fancy signal processing based methods to address the problem. 

Let me add three methods you have not mentioned that are classic and more statistical in nature: least squares, ridge regression and lasso.