Field Aware Factorization Machines
Suppose (prior to one-hot-encoding) you have predictors/fields from a set $Z$ (say movie genre, user gender, and user race).  Suppose further, each predictor $z \in Z$ can take on one of $k_z$ values.  After one-hot encoding, you will have a new set of binary features $X$ of size $K := \sum_{z \in Z}k_z$.

In a model with all interactions, you must estimate a matrix of interaction coefficients $Q$, which has $K\times (K+1) / 2$ unique terms.

The factorization machine puts structure on the matrix $Q$, and assumes that $Q \equiv W^{T} W$, where $W$ is of dimension $l \times K$, with $1\le l \le K$ some number specified by the user.  We estimate $W$ instead of $Q$.

The field-aware factorization machine puts structure on $Q$ as well.  It partitions $Q$ into blocks based on $z$ (the original features).  If $q_{z_i, z_j}$ denotes the $z_i,z_j$ block of $Q$, we assume that $q_{z_i,z_j}$ comes from the $z_i,z_j$ block of $W_j^{T} W_i$, where $W_i$ is of dimension $l \times K$.  As with the FM, we estimate the $W_i$ instead of $Q$.

The FM factorization of $Q$ has $K \times l $ parameters.  The "feild-aware" FM has $K\times l\times |Z|$ parameters.  A model with all interactions has $K \times (K+1)/2$ parameters.