(EDIT: cross-posted at https://mathoverflow.net/questions/452658/min-norm-solution-of-over-specified-linear-system-of-p-adic-equations after 1 week without receiving any answer.)
Let $A \in \mathbb{Q}_p^{n \times d}$ be a matrix with $p$-adic entries, with $n\ge d$, and $b \in \mathbb{Q}_p^{n}$ be a vector. I want to find $x \in \mathbb{Q}_p^d$ which minimizes $\|Ax - b\|_p := \max_{i} |a_i^T x - b_i|_p$ where $|.|_p$ is the p-adic absolute value. Equivalently, I want to find the smallest $k \in \mathbb{Z}$ and $x \in \mathbb{Q}_p^d$ such that $a_i^T x \equiv b_i \,\, (\mathrm{mod} \,\, p^{k})$ for $i=1, \ldots, n$.
Idea (for the particular case $A \in \mathbb{Z}^{n \times d}$ and $b \in \mathbb{Z}^n$):
Randomly pick $d$ rows of $A$ and corresponding entries in $b$ (say $A_d \in \mathbb{Z}^{d \times d}$ and $b_d \in \mathbb{Z}^d$) such that $\det(A_d) \not\equiv 0\,\, (\mathrm{mod}\,\, p)$ and solve $A_d x \equiv b_d \,\, (\mathrm{mod} \,\, p)$ Let $x^*$ be this solution (which I believe must exist and be unique modulus $p$).
For $k=1, 2, \ldots$
- Check if solution satisfies held-out equations, i.e., if $Ax^* \equiv b \,\, (\mathrm{mod} \,\, p^k)$. If not, return $k-1$.
- Solve $A_d x \equiv b_d \,\, (\mathrm{mod} \,\, p^{k+1})$. This can be done by lifting the previous solution. Set $x^*$ to be this new solution.
Is this procedure correct? Is there a more efficient procedure? Can we generalize this idea to $A \in \mathbb{Q}_p^{n \times d}$ and $b \in \mathbb{Q}_p^{n}$? What if $\mathrm{det}(A_d) = 0$ for any possible choice of $d$ rows?
Thank you.