In this post, you can find some helpful mathematical tips and tricks in the Python programming language.

Linear separability⌗

Two sets $ A $ and $ B $ in an $ n $ dimensional Euclidean space are linear separable if there exist $ n + 1 $ numbers $ w_i \in \mathbb{R} $ such that every point $ a \in A $ satisfies

$$ \sum_{i=1}^{n}w_i a_i > k, $$

and every point $ b \in B $ satisfies

$$ \sum_{i=1}^{n}w_i b_i < k, $$

where $ k \in \mathbb{R} $ defines a linear border (e.g., a line) between data points of the two sets.

In layperson’s terms, let’s say we have two two-dimensional data sets (e.g., each data point is described by two coordinates, x and y). These two sets are linearly separable if we can draw at least one line that will separate the points of set A from those of set B.

Many times we have to solve a classification or clustering problem. If we could know a priori if the involved sets are linearly separable, we could choose the appropriate classification algorithm. For instance, if the data sets are not linearly separable, we won’t be able to use a linear classifier.

Therefore, one way to know if the sets at hand are linear separable is to compute the convex hull of each set and check if those convex hulls intersect or one contains the other, or they overlap. If any of those three conditions is true, then we know that the two sets are not linearly separable. In Python, we can quickly check that using the function ConvexHull of Scipy. Here is an example:

import matplotlib.pylab as plt

from sklearn.datasets import make_moons, make_blobs
from scipy.spatial import ConvexHull


if __name__ == '__main__':
    S = 8       # size of scatter plot point
    blobs = make_blobs(n_samples=100, centers=2, random_state=13)
    moons = make_moons(n_samples=100)

    fig = plt.figure(figsize=(13, 11))
    ax1 = fig.add_subplot(221)
    Xb, Yb = blobs
    x1b = Xb[Yb == 0]
    x2b = Xb[Yb == 1]
    ax1.scatter(x1b[:, 0], x1b[:, 1], s=S)
    ax1.scatter(x2b[:, 0], x2b[:, 1], c="orange", s=S)
    ax1.set_xticks([])
    ax1.set_yticks([])

    ax2 = fig.add_subplot(222)
    X, Y = moons
    x1 = X[Y == 0]
    x2 = X[Y == 1]
    ax2.scatter(x1[:, 0], x1[:, 1], s=S)
    ax2.scatter(x2[:, 0], x2[:, 1], c="orange", s=S)
    ax2.set_xticks([])
    ax2.set_yticks([])

    ax3 = fig.add_subplot(223)
    ch1 = ConvexHull(x1b)			# Compute the convex hull
    ax3.scatter(x1b[:, 0], x1b[:, 1], s=S)
    ax3.plot(x1b[ch1.vertices, 0], x1b[ch1.vertices, 1], lw=2, c='k')
    ch2 = ConvexHull(x2b)
    ax3.scatter(x2b[:, 0], x2b[:, 1], s=S)
    ax3.plot(x2b[ch2.vertices, 0], x2b[ch2.vertices, 1], lw=2, c='k')
    ax3.set_xticks([])
    ax3.set_yticks([])

    ax4 = fig.add_subplot(224)
    ch1 = ConvexHull(x1)
    ax4.scatter(x1[:, 0], x1[:, 1], s=S)
    ax4.plot(x1[ch1.vertices, 0], x1[ch1.vertices, 1], lw=2, c='k')
    ch2 = ConvexHull(x2)
    ax4.scatter(x2[:, 0], x2[:, 1], s=S)
    ax4.plot(x2[ch2.vertices, 0], x2[ch2.vertices, 1], lw=2, c='k')
    ax4.set_xticks([])
    ax4.set_yticks([])

    plt.savefig("convec_hulls.png")
    plt.show()
Figure 1. Blobs and moons data sets along with their convex hulls. The blobs are linear separable since the convex hull of the blue set does not intersect or overlap with the convex hull of the orange data set. On the other hand, the moons data set is not linear separable.

Positive definite matrix⌗

Check if a given matrix $ \bf{A} $ is positive definite. If all the eigenvalues of matrix $ \bf{A} $ are positive then the matrix is positive definite.

$ A = np.array([[1, 2], [2, 1]])
$ print(A)
[[1 2]
 [2 1]]

$ np.all(np.linalg.eigvals(A) > 0)
False       # A is not a positive definite matrix

$ A = np.array([[2, -1, 0], [-1, 2, -1], [0, -1, 2]])
print(A)
[[ 2 -1  0]
 [-1  2 -1]
 [ 0 -1  2]]

$ np.all(np.linalg.eigvals(A) > 0)
True        # A is positive definite

Random matrix with predetermined condition number⌗

You can generate a random matrix with predetermined condition number by following method:

$ cond = 3.0
$ n, m = 3, 2
$ A = np.random.normal(0, 1, (m, n))
$ print(A)

[[ 0.24143692 -0.61944458]
 [ 0.49427012  1.34003024]
 [-1.08271826  0.91021725]]

$ k = min(m, n)
$ U, S, V = np.linalg.svd(A)

$ S = S[0] * (1.0 - ((cond - 1.0) / cond) * (S[0] - S) / (S[0] - S[-1]))

$ SMAT = np.zeros((m, n), dtype=complex) + 1e-9
$ smat[:k, :k] = np.diag(S)

$ B = U @ (SMAT @ V.T)

$ print("Desired condition number: ", cond)
Desired condition number: 3.0
$ print("Actual condition number", np.linalg.cond(B))
Actual condition number: 2.9999999999999973

Integer operations⌗

Fast integer division by two (rounded down). In this case, we have to perform a bit shift to the right by $ k $. $ k $ indicates the power of two $ 2^k $.

# n >> k

$ 6 >> 1
3
$ 6 >> 2
0

Fast integer multiplication with two by left-bit-shift.

# n << k

$ 6 << 1
12
$ 6 << 24

Check if an integer $ n $ is even or odd by performing a binary and operation. If the result of the following operation is 0, then n is even, otherwise is an odd number.

# n & 1

$ 6 & 1
0
$ 5 & 1
1

You can find the maximum power-of-two that divides an integer $ n $ by performing an and operation between the integers $ n $ and its additive inverse $ -n $.

# -n & n

$ -5 & 5
1
$ -6 & 6
2
$ -12 & 12
4