Estimating Convolution Input Under the Assumption of Sparsity and Constant Non Zero Values Using Compressive Sensing Approach
Basically your problem is called Blind Deconvolution.
It means we want to estimate both the operator and the input given the output.

You model is Linear Time Invariant Operator so we have LTI Blind Deconvolution.
In general blind deconvolution is ill poised problem.
So we need to make assumptions about the model. The more assumptions the better the chance to solve this really hard problem.

What do we have in your case:


The input signal is sparse.
The input signal has 2 values, either zero or other known value.


What's missing is some assumptions on the operator $ h $.  

Deconvolution in Image Processing

The field which pushes the deconvolution problem farther and farther is mostly the image processing field.
There are many models of real world images and convolution kernels.

Let's talk about the most common for each:


In most cases the convolution kernel is assumed to be LPF with its sum of coefficients equal 1 and each coefficient is non negative.
In most cases the image is assumed to be "Piece Wise Smooth. Enforcing it using the Total Variation Model which basically says the Gradients are distributed according to Laplace Distribution. 


With those 2 models we can model the problem as:

$$\begin{aligned}
\arg \min_{h, x} \quad &amp; \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) \\
\text{subject to} \quad &amp; \sum h = 1 \\
&amp; {h}_{i} \geq 0 \\
\end{aligned}$$

As can be seen this is highly non convex problem. The method used to solve it is by splitting methods.

So we solve it by iterations:

We set $ {h}_{i}^{0} = \frac{1}{N} $, then:


For the estimated signal:


$$\begin{aligned}
{x}^{k + 1} = \arg \min_{x} \quad &amp; \frac{1}{2} {\left\| {h}^{k} \ast x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) \\
\end{aligned}$$


For the estimated kernel:


$$\begin{aligned}
{h}^{k + 1} = \arg \min_{h} \quad &amp; \frac{1}{2} {\left\| h \ast {x}^{k + 1} - y \right\|}_{2}^{2} \\
\text{subject to} \quad &amp; \sum h = 1 \\
&amp; {h}_{i} \geq 0 \\
\end{aligned}$$

So, in your case we can do the following:


Replace the regularization by the Sparsity Model. Solve the $ x $ iteration by the methods in Thomas' answer (Yaghoobi, Blumensath, Davies, 2007, Quantized Sparse Approximation with Iterative Thresholding for Audio Coding - DOI,  Nagahara, 2015, Discrete Signal Reconstruction by Sum of Absolute Values - DOI). Solve for $ h $ as for Least Squares with Simplex Constraint.
Use model without convolution using Dictionary and use Dictionary Learning Methods like K-SVD. For the signal estimation iteration still you should use the methods above.


Some related questions:


Using Total Variation Denoising to Clean Accelerometer Data.
The Meaning of the Terms Isotropic and Anisotropic in the Total Variation Framework.
Why Sparse Priors Like Total Variation Opts to Concentrate Derivatives at a Small Number of Pixels?
How Can I Use MATLAB to Solve a Total Variation Denoising / Deblurring Problem?
Intuitive Meaning of Regularization in Imaging Inverse Problems.
Estimation / Reconstruction of an Image from Its Missing Data 2D DFT.
Deconvolution of an Image Acquired by a Square Uniform Detector.