In his 2004 paper, "Non-negative Matrix Factorization with Sparseness Constraints," Patrick Hoyer introduced a function that measures the sparseness of a nonzero vector. The paper does not explain or motivate the formula, so this article describes the geometry and intuition behind Hoyer's formula, along with a visualization and examples. Hoyer's sparseness measure has been used to analyze matrix factorizations and to interpret spectra in mass spectrometry.

Sparseness versus sparsity

First, I want to clarify the difference between Hoyer's definition of sparseness (for a vector) and the traditional notion of sparsity (for a matrix).

In numerical analysis, a matrix is said to be sparse if most of its elements are exactly zero and only a few elements are nonzero. For example, a large diagonal (or tridiagonal matrix) is sparse because the only nonzero elements are on (or near) the diagonal, and other elements are exactly zero. The sparsity of a matrix is reported as the proportion of elements that are zero. For an n x m, this is card(A[i,j] = 0) / (n*m), which is a number in [0,1]. Very sparse matrices have sparsity close to 1, whereas very dense matrices have sparsity close to 0. An n x n diagonal matrix has sparsity 1 – 1/n.

Hoyer's measure of sparseness is for vectors, not matrices. It does not count zeros and non-zeros. Rather, it looks at the magnitudes of the elements and measures how many are relatively large and how many are relatively small. If all elements are approximately the same magnitude, the vector has a sparseness measure that is close to 0. If there are a small number of large elements and the other elements are small, the vector has a measure that is close to 1.

Hoyer's sparseness measure

Hoyer's sparseness measure is defined as follows. If v ≠ 0 is an n-dimensional vector, n ≥ 2, the sparseness of v is defined as
      $S(v) = \frac{\sqrt{n} - \|v\|_1 / \|v\|_2}{\sqrt{n} - 1}$
where $\|v\|_1 = \sum_{i=1}^n |v_i|$ is the L₁ vector norm, and $\|v\|_2 = \sqrt{ \sum_{i=1}^n v_i^2 }$ is the L₂ or Euclidean norm.

Clearly, the ratio of the L₁ norm to the L₂ norm is an important quantity. There are a few easy mathematical results about the ratio $\|v\|_1 / \|v\|_2$:

1. The ratio is invariant under a change of signs for any component. That is, if S is a diagonal matrix whose diagonal elements are ±1, then $\|S v\| = \|v\|$.
2. The ratio is scale invariant. For any c ≠ 0, scalar multiplication by c does not change the ratio: $\|c v\|_1 / \|c v\|_2 = \|v\|_1 / \|v\|_2$.
3. The ratio is permutation invariant because the norms are permutation invariant. That is, if you permute the coordinates of v, you do not change the norm or the ratio of norms. In terms of matrices, if P is any permutation matrix, $\|P v\| = \|v\|$.

The first property tell you that it suffices to understand the ratio of norms for "positive vectors" in the first octant (that is, all components are positive). The second property tells you that you can standardize the vectors to have unit L₂ norm. The third property tells you that you can assume that |v₁| ≥ |v₂| ≥ … ≥ |v₂|, if you want to. These properties are apparent in the subsequent visualizations.

The range of the Hoyer measure

For any nonzero n-dimensional vector, the Hoyer measure of sparseness is in the interval [0, 1].

The Hoyer measure achieves its maximum value of 1 when (n-1) components of v are zero and the remaining component is nonzero. The properties in the previous section enable us to assume, without loss of generality, that the first component is nonzero. Then, ||v||₁ = ||v||₂, so the ratio of norms is 1. It follows that S(v) = 1 when v has only one non-zero component.

The Hoyer measure achieves its minimum value of 0 when all components of v are equal. The properties in the previous section enable us to standardize the vector so that its Euclidean norm is 1. If all components are equal, then ||v||₂ = sqrt(Σ a²) = 1 for some value, a. Thus, a = ±1/sqrt(n). Consequently, ||v||₁ = n / sqrt(n) = sqrt(n), so the numerator of Hoyer's measure vanishes. It follows that S(v) = 0 when all components of v are equal.

Examples of Hoyer's sparseness

Let's illustrate this concept with an example. Consider the following 6-D vectors. To within four decimal places, the Euclidean (or L2) norm of each vector is 1.

• q = {0.4082, 0.4082, 0.4082, 0.4082, 0.4082, 0.4082}. The L1 norm is 2.4492, and the Hoyer sparseness is 0.
• s = {0.5774, 0.5774, 0.5774, 0, 0, 0}. The L1 norm is 1.7322, and the Hoyer sparseness is 0.4950.
• u = {0.9948, 0.08, 0.04, 0.04, 0.02, 0.02}. The L1 norm is 1.1948, and the Hoyer sparseness is 0.8656. Notice that the sparseness is high even though no element is exactly 0.

The panel of graphs to the right visualizes the meaning of Hoyer's sparseness measure. Vectors that have a few elements that are larger than the other have the most sparseness. Vectors whose components are approximately uniformly distributed have the least sparseness.

Visualize Hoyer's sparseness for 2-D vectors

Since Hoyer's measure is invariant under scaling, it suffices to visualize the measure for unit vectors. If the vectors are two-dimensional, the unit vectors are on the unit circle centered at the origin. From the previous section, we know that the measure will obtain its maximum value of 1 for vectors that are aligned with a coordinate axis. It will obtain its minimum value of 0 when the components are equal in magnitude. In the first quadrant, this occurs when the vector makes an angle of 45 degrees or π/4 radians. By the permutation invariance, there are also minima for vectors at 3π/4, 5π/4, and 7π/4 radians.

The following SAS DATA step visualizes the Hoyer sparseness measure for 2-D vectors on the unit circle:

/* A measure of sparsity of a vector from:
   Patrick O. Hoyer. Non-negative matrix factorization with sparseness constraints. 
                     Journal of Machine Learning Research, 5:1457–1469, 2004.
   The "most sparse" vector is one for which only a single component is non-zero.
   That is, it aligns with a coordinate axis. These vectors have a sparseness measure of 1.
   The "least sparse" vector is one for which elements are equal. These vectors have a sparseness of 0.
*/
/* first, visualize for v on the unit circle in 2-D */
data circle_Hoyer;
   sn = sqrt(2);
   pi = constant('pi');
   do theta = 0 to 2*pi by pi/100;
      x = cos(theta);
      y = sin(theta);
      L1 = lpnorm(1, x, y);  /* L1 norm of v=(x,y) */
      Sparseness = (sn - L1) / (sn-1);
      output;
   end;
run;
 
/* use Spectral color ramp from ColorBrewer */
%let spectral = CX3288BD CX99D594 CXE6F598 CXFFFFBF CXFEE08B CXFC8D59 CXD53E4F;
/* Visualize Hoyer's sparseness measure on the unit circle */
title "Sparseness on the Unit Circle";
proc sgplot data=circle_Hoyer aspect=1;
   scatter x=x y=y / colorresponse=Sparseness colormodel=(&spectral) markerattrs=(symbol=CircleFilled);
   gradlegend / title="L1 Norm";
   xaxis grid; yaxis grid;
run;

As expected, the visualization shows that the Hoyer sparseness measure is 0 (blue) for the vectors (±1/√2, ±1/√2), which have components that are equal in magnitude. The measure is 1 (red) for vectors on a coordinate axis. Notice that I used the LPNORM function in Base SAS to compute the L1 norm of the vectors.

Visualize Hoyer's sparseness for 3-D vectors

In a similar way, you can visualize the sparseness of 3-D unit vectors. The measure will obtain its maximum value of 1 for vectors that are aligned with a coordinate axis. It will obtain its minimum value of 0 when the vectors components are equal in magnitude: (±1/√3, ±1/√3, ±1/√3).

The following SAS DATA step visualizes the Hoyer sparseness measure for 3-D vectors on the upper hemisphere of the unit sphere:

/* Generate the grid for the upper hemisphere */
data sphere_L1;
   sn = sqrt(3);
   delta = 2**(-5);     /* Set the resolution of the grid */
   /* Loop over (x,y) in unit circle, subset of [-1,1]x[-1,1] */
   do x = -1 to 1 by delta;
      do y = -1 to 1 by delta;
         if (x**2 + y**2) <= 1 then do; /* restrict to unit circle */
            z = sqrt(1 - x**2 - y**2);  /* upper hemisphere */
            L1 = lpnorm(1, x, y, z);    /* L1 norm of v=(x,y,z) */
            Sparseness = (sn - L1) / (sn-1);
            output;
         end;
      end;
   end;
   drop delta;
run;
 
/* use Spectral color ramp from ColorBrewer */
%let spectral = CX3288BD CX99D594 CXE6F598 CXFFFFBF CXFEE08B CXFC8D59 CXD53E4F;
/* Visualize the L1 norm as a heatmap */
title "Heatmap of Sparseness on the Upper Hemisphere of the Unit Sphere";
proc sgplot data=sphere_L1 aspect=1;
   heatmapparm x=x y=y colorresponse=Sparseness / colormodel=(&spectral);        
   gradlegend / title="L1 Norm";
run;

Because of the symmetries in the Hoyer sparseness measure, it suffices to visualize the measure on vectors in first octant where all elements are nonnegative. In the following image, I used a DROPLINE statement to locate the vector that has minimal Hoyer sparseness, which is (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)).

A SAS function to compute Hoyer's sparseness

In SAS, the IML language is the natural place to implement a vector measure because the language supports vector operations in a natural way. The following PROC IML statements define a function that computes Hoyer's sparseness for a vector:

proc iml;
/* Hoyer's sparseness measure.
   For a column vector, v, this function returns 
   the Hoyer (2004) measure of sparseness
   s = (sqrt(n) - ||v||_1 / ||v||_2) / (sqrt(n)-1)
*/
start Sparseness(v);
   u = colvec(v);    /* always treat input as a column vector */
   L2 = norm(u, "L2");
   if L2=0 then return(.);
   L1 = norm(u, "L1");
   sn = sqrt( countn(u) );
   sparseness = (sn - L1/L2) / (sn - 1);
   return( clip01(sparseness) );
finish;
/* Helper function: clip values into [0,1]
   If x is any matrix, return a new matrix whose i_th element has the value 
   0    if x[i] < 0
   x[i] if 0 <= x[i] <= 1
   1    if x[i] > 1
   See https://blogs.sas.com/content/iml/2026/02/04/clip-values.html */
start clip01(x);
   return( 0 <> (x >< 1) );
finish;
 
/* Examples: Compute the Hoyer measure for these columns */
/*   q       r  s       t    u       v */  
A = {0.4082  1  0.5774  3.3  0.9948  1,
     0.4082  1  0.5774  1    0.08    0,
     0.4082  1  0.5774  1    0.04    0,
     0.4082  1  0       0.3  0.04    0,
     0.4082  1  0       0.2  0.02    0,
     0.4082  1  0       0.2  0.02    0};
 
S = j(1, ncol(A), .);
do i = 1 to ncol(A);
   S[i] = Sparseness( A[,i] );
end;
print S[F=6.4 c=('q':'w') L="Hoyer's Sparseness"];

The table shows the sparseness for each column of the A matrix.

• The first and second columns (q and r) both have sparseness 0 because both columns are constant in value. The first column has unit L2 norm whereas the second column does not. But it doesn't matter, because the Hoyer measure is normalized by using the ratio ||v||₁ / ||v||₂.
• The third column (s) has three zero elements and three equal and nonzero elements. The sparseness measure is 0.495.
• The fourth column (t) has one large element, two medium-sized elements, and three small but nonzero elements. The sparseness measure is 0.5445.
• The fifth column (u) has one large element and five small but nonzero elements. The sparseness measure is 0.8656.
• The last column (v) has one large element and five elements that are zero. The sparseness measure is 1, which is the largest possible value of sparseness.

An earlier section visualized three of these columns in a panel of needle plots.

Summary

This article introduces the Hoyer sparseness measure, S(v), for nonzero vectors v. The measure indicates whether a vector has many components that are the same magnitude (low sparseness) as opposed to vectors that have many small components and only a few components that are large in magnitude. The sparseness measure is invariant to scaling, permutation of components, and switching the signs of components. Accordingly, you can visualize the measure by using vectors whose components are all positive and whose Euclidean length is 1.

A future article shows an application of the Hoyer measure to the nonnegative matrix factorization (NMF) method.