Solving linear system with zero constraint

Question

I have a classification system that can be described by the matrix $A$ where $A_{i,j}$ is the probability that an object of class $j$ will be classified as class $i$.

Given the true class counts $x$, the estimated class counts, $y$, can be modelled as $Ax = y$. Thus I can estimate the true class counts from the output of the classifier as $A^{-1}y$. Going further, I can enforce a positive count constraint by using a non-negative linear solver such as scipy.optimize.nnls.

Let's say I know that some values of $x$ are definitely zero. How can I add that constraint?

My current thoughts are to remove the columns of $A$ and values of $x$ corresponding to the zero counts. For example, if there are 5 classes and 2 should be zero, we would have $A$ with dimensions (5,3), $x$ with dimension 3 and $y$ with dimension 5. The system is now over-determined, how could I solve it?

Answer 1

What now if you have more equations than unkonwns? What if you have 5 points in time where you have measured the quantity $y$, but you still want to fit the other 3 parameters $x$. In general, there is no solution to a system of 5 equations with 3 unknowns, unless you are very lucky. A common approach is to try to find the four parameters that fit the 5 equations as good as possible. One way to do this is to find the four parameters such that the sum of the squares of the errors between the specified right-hand-side and the computed right-hand-side is as small as possible. It is very easy to do this with numpy. You can simply specify a matrix with M rows and N colums where M is larger than N (so more rows than columns). Combined with a right-hand-side with M values, you can find a least-squares solution that best fits the equations. Use the np.linalg.lstsq function to compute a solution. Note that the np.linalg.lstsq solution returns four things, of which the first one is the least squares solution (use np.linalg.lstsq? to find out what else is returned).

An example to plot a continious line with 6 datapoint, 4 parameters and the function: $y=a*cos(πt)+b*cos(2πt)+c*cos(3πt)+d*cos(4πt)$

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

# Datapoints
tp = ([0.9, 1.2, 0.6, 1.6, 1, 1.7])
yp = ([-0.4, 0.6, -1, 0, -0.8, 0.2])
A = np.zeros((6,4))
rhs = np.zeros(6)

#Filling matrix A and rhs
for i in range(len(tp)):
    A[i] = np.cos(np.pi * tp[i]), np.cos(2 * np.pi * tp[i]), np.cos(3 * np.pi * tp[i]), np.cos(4 * np.pi * tp[i])
    rhs[i] = yp[i]

#Solutoin
sol, residuals, rank, s = np.linalg.lstsq(A, rhs)
print(sol[0])

#Plotting
plt.plot(tp, yp, 'ro', label = 'dots')
t = np.linspace(0, 2, 100)
y = sol[0] * np.cos(np.pi * t) + sol[1] * np.cos(2 * np.pi * t) + sol[2] * np.cos(3 * np.pi * t) + sol[3] * np.cos(4 * np.pi * t) 
plt.plot(t, y, label = 'approx. function')
plt.legend(loc='upper center')(t, y);