I am trying to find the homography that maps a certain image to another related image. This can be done by selecting at least $4$ point-to-point correspondences, then we can solve a constrained problem of the form $\operatorname{argmin}\|\mathbf{A}\mathbf{h} \|$ subject to $\|\mathbf{h}\|=1$, which, it turns out, can be solved by computing the singular value decomposition of $\mathbf{A}$, and then the solution is one of the right singular vectors of $\mathbf{A}$.
In my case, one of the images is distorted. More specifically, certain (or all) straight-lines in the real-world have become other curves (apparently, parabolas, so second-degree polynomials). I read certain parts of the book Multiple view geometry in computer vision by Richard Hartley and Andrew Zisserman, specifically, the parts related to the properties of the different types of invariants of specific homographies, such as Euclidean transformations, similarities, affinities and the most general homographies (which do not even preserve lines at infinity). Even after having read those sections, I am still not sure whether homographies can map straight-lines (one-degree polynomials) to second-degree polynomials (e.g. parabolas), and so if I can find a homography that maps one image to the other. I think homographies cannot convert lines to parabolas, because, AFAIK, homographies are linear transformations and only linear transformations can be homographies, but, apart from that, I would not have an intuitive explanation for this.
So, can a homography transform a straight-line into another type of curve? What's the intuition and can this be mathematically proved?
It seems like there are really two questions here. The first is “What is the image of a line under a homography?” You’ve already answered that one yourself: If we have $x'=Hx$, then $$l^Tx = l^T(H^{-1}H)x = (H^{-T}l)^T(Hx) = 0,$$ so the image of every point on the line $l$ lies on $H^{-T}l$ and every point on $H^{-T}l$ is the image of some point on $l$. In fact, this is one of the key characterizations of a projective transformation: it preserves colinearity. Some sources even define projective transformations in this way.
The second question is essentially whether a conic can contain an entire line. The answer is yes, but only if the conic is degenerate. So, in particular, no line is contained in its entirety by a parabola, ellipse or hyperbola. Since, per the preceding paragraph, the image of a line is a line, this means that a line can’t be turned into a parabola by a projective transformation.
For the proof, I’ll follow Jürgen Richter-Gebert’s Perspectives on Projective Geometry, §9.2:
Proof: If the solution set of $q^TAq=0$ contains an entire line $l$, then it can be factored into the product of two linear factors which we can write as $(q^Tl)(g^Tq)=0$. This in turn can be interpreted as $q^T(lg^T)q = 0$, which is a quadratic form with a nonsymmetric rank-one matrix $M=lg^T$, which we symmetrize by replacing it with $M+M^T$. If $g=\lambda l$, then $M+M^T$ is also rank-one, hence $\det(M+M^T)=0$. On the other hand, if $l$ and $g$ are linearly independent, then $$(M+M^T)(g\times l) = (lg^T+gl^T)(g\times l) = l\langle g,g\times l\rangle + g\langle l,g\times l\rangle = 0.$$ (Here, $\langle\cdot,\cdot\rangle$ denotes the usual Euclidean inner product.) Thus, $M+M^T$ has a nontrivial null space, so its determinant vanishes. To complete the proof, we note that $M+M^T$ must be a multiple of $A$.
(You might recall that $g\times l$ is the intersection point of the two lines, so that last equation also says that this point lies on the conic—nothing particularly mysterious there.)