Nuclear norm

A norm is a property of a vector that binds the vector to its quantifiable length. Simply put, we can say that a norm allows us to think of a vector in terms of distance i.e. how long it is.

Norms are highly useful in fields such as physics, engineering, and computational mathematics.

Norms in vector spaces

We can think of a norm as a function that takes an object as input and returns a non-negative scalar value as its output. In the context of vector space, the norm is used to measure the size of a vector.

There is a diverse range of norms that exists in the mathematical world. There are different types of norms because they capture the varying aspects of the mathematical objects being measured. The choice we ultimately take depends on our individual needs and the application at hand.

Let's say we have a two-dimensional space. Then the norm of a $vector (x, y)$ will be given by the formula $√(x^2 + y^2)$ , which is the Euclidean norm.

Today we will be discussing a type of norm called nuclear norm in our answer.

Nuclear norms

A nuclear norm of $Y$ is the sum of singular values of a given vector $Y$ or matrix $Y$. Nuclear Norms are also mainly used to measure the size or the complexity of a matrix.

Before we fully explore nuclear norms, let's understand singular values first. Suppose we have a matrix $A$. The singular values of $A$ are the square roots of the eigenvalues of the matrix $A^T * A$ or the matrix $A * A^T.$ eigenvalues

The eigenvalues must be sorted in a decreasing order before taking their square roots. These values are crucial to demonstrating the magnitude of a vector.

Note: Singular values always belong to real numbers.

Now that we understand singular values, we can think of the nuclear norm as the function of taking the sum of all these individual values.

It can be mathematically expressed as:

Formula breakdown

• $‖Y‖∗$ denotes the nuclear norm of matrix $Y$.

• $σj(Y)$ denotes the $jth$ singular value of matrix $Y$.

Therefore, the sum of each singular value is added to the nuclear norm variable.

First Python implementation

Explanation

• Line 1: Since we will be storing the values of the matrix in an array, we have to import the numpy library which makes applying operations on arrays faster. The alias name for numpy is conventionally taken as np.

• Line 3: We define a function called nuclearNorm that takes in a matrix as a parameter and returns its nuclear norm value

• Lines 4 – 5: np.linalg.svd is a function in the linear algebra module of numpy that computes singular value decomposition on the values of the matrix. We pass false to the compute_uv parameter since we do not require the left and right singular matrices. Since the nuclear norm is the sum of the singular values, we will simply call np.sum(singularVals) to save the value in nuclearNormVal.

• Line 6: We return the calculated nuclearNormVal value.

• Line 8: We define a 3 x 3 matrix with some starting values and save it in a 2D array.

• Line 9: We call the nuclearNorm method on our matrix and finally print the results.

Second Python implementation

Explanation

For the sake of simplicity, let's use the same matrix we defined above.

We use the simple norm function provided by the linalg (linear algebra) module and pass a parameter ord the value of nuc.

• ord refers to the order of the norm.

• value of nuc means we want a norm of the order nuclear norm.

Use cases of nuclear norm

Matrix completion

Nuclear norms can be pretty helpful in finding corrupted elements in a partially observed matrix.

Robust Principal Component Analysis

This is a technique that separates a matrix into low-rank and sparse components. We can utilize the nuclear norm here to encourage low ranks and the sparse components can be used to find the outliers in data. For instance, video surveillance and image denoising.

Graph analysis

Nuclear norm regularization is a technique that is used in graph analysis problems. We can solve problems like graph completion and link prediction as well as finding missing links.