Suboptimal Solution for a combinatorial problem
If you are willing to replace the induced $2$-norm with the Frobenius norm, then you can solve the problem column-by-column instead of all at once. 

In a lot of practical situations I would expect the frobenius minimizer will be exactly the 2-norm minimizer, and is a common choice of norm to minimize in matrix completion problems.



edit: In a recent edit the original poster made it clear that what they are looking for is the frobenius norm, even though the notation $||\cdot||_2$ is traditionally used for the induced 2-norm. (the edit makes the problem much less interesting). Since the rest of this post is about justifying the Frobenius norm as an approximation to the induced 2-norm, it's basically irrelevant to the edited version of the question.

A little bit more on why the Frobenius norm could be a good approximation.

Since all norms are equivalent on a finite dimensional space, immediately we have
$$c(s)||\hat{X} - X||_{Fro} \le ||\hat{X} - X||_2 \le C(s) ||\hat{X} - X||_{Fro},$$

so the Frobenius minimizer will be within a constant of the $2$-norm minimizer when the dimensions of the matrix are fixed. The issue, as usual, is that the constants $c(s), C(s)$ depend on the number of entries in the matrix and go to zero/blow up as $s$ becomes larger and larger.

However, there is a situation where the constants do not blow up and that is, roughly, when 


you are dealing with a sequence of matrices $\hat{X}_s, B_s$ that are stably larger and larger approximations of some extremely high dimensional (or infinite dimensional) true matrices (operators) $\hat{X},B$, and
the very large or infinite "true" problem has a solution in the sense that there exists $X_{optimal}$ such that $\hat{X} - X_{optimal}$ is compact.


A little bit more on these conditions: 1) is the case if, for example


your matrices are generated by incomplete sampling of data (eg., measurements from a scientific experiment where you could get better results by taking more data, or shopping data from a small subset of amazon's customers that are supposed to represent the customerbase as a whole), and you could get similar but bigger problems from the same distribution just taking more samples, or
the size $s$ of your matrices comes from the level of discretication of a continuum problem like a partial differential equation.


Furthermore, 2) must always be the case if you reasonably expect a solution, since if there is no approximation that makes $\hat{X} - X$ compact, then by definition it has no finite rank approximation, so you can never come up with a good result to the real problem by solving limited data versions with $\hat{X}_s, B_s$ nomatter how big $s$ is.

Now, assuming that the compactness condition holds, the singular values $\sigma_1, \sigma_2, \dots$ of $\hat{X} - X_{optimal}$ are summable (and thus square summable), and so we have the explicit equivalence,
$$||\hat{X} - X_{opt}||^2_{Fro} = \sum_{i=1}^{\infty} \sigma_i^2 = \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)\sigma_1^2 =  \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X} - X_{opt}||_2^2.$$

These constants are independent of $s$, and moreover the more compact the error, the faster the singular values decay, so the closer to 1 the equivalence constant is. Thus assuming that the matrices $\hat{X}_s, B_s$ come from stable sampling schemes or stable discretizations of $\hat{X},B$, we have the equivalence
$$||\hat{X}_s - X_{s,opt}||^2_{Fro} \le \gamma_1\left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X}_s - X_{s,opt}||_2^2 \le \gamma_2  ||\hat{X}_s - X_{s,opt}||^2_{Fro},$$
where $\gamma_1$, $\gamma_2$ come from the stability and coercivity constants of the sampling/discretization process.

So, since the assumptions above apply to a wide range of circumstances, replacing $2$-norm minimization with Frobenius norm minimization often makes sense in practical contexts.