{'fraction_non_alphanumeric': 0.02963855421686747, 'fraction_numerical': 0.016144578313253014, 'mean_word_length': 4.796438547486034, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Nonnegative Matrix Factorization with Toeplitz Penalty

Nonnegative Matrix Factorization (NMF) is an unsupervised learning algorithm that produces a linear, parts-based approximation of a data matrix. NMF constructs a nonnegative low rank basis matrix and a nonnegative low rank matrix of weights which, when multiplied together, approximate the data matrix of interest using some cost function. The NMF algorithm can be modified to include auxiliary constraints which impose task-specific penalties or restrictions on the cost function of the matrix factorization. In this paper we propose a new NMF algorithm that makes use of non-data dependent auxiliary constraints which incorporate a Toeplitz matrix into the multiplicative updating of the basis and weight matrices. We compare the facial recognition performance of our new Toeplitz Nonnegative Matrix Factorization (TNMF) algorithm to the performance of the Zellner Nonnegative Matrix Factorization (ZNMF) algorithm which makes use of data-dependent auxiliary constraints. We also compare the facial recognition performance of the two aforementioned algorithms with the performance of several preexisting constrained NMF algorithms that have non-data-dependent penalties. The facial recognition performances are evaluated using the Cambridge ORL Database of Faces and the Yale Database of Faces.


Introduction
In the last several decades, facial detection and recognition via algorithmic-based approaches have become quite popular. These tasks are often complicated due to variation in illumination, orientation, emotional expression and physical location of a face within an image. With the rise of big data, facial databases have become massively large. This has further complicated the already complex tasks of facial detection and recognition. The need to process these large and complex datasets has caused a surge in the utilization of subspace methods, such as nonnegative matrix factorization (Paatero and Tapper [12], and Seung and Lee [16]). These methods are used for the purpose of reducing data dimensionality while simultaneously identifying and preserving latent underlying structure in the dataset.
For facial databases, the data matrix X contains p vectorized images, each containing n pixel value intensities. The NMF algorithm produces an approximate representation of the nonnegative data matrix X ∈ R n×p in the form of a matrix product: The NMF problem can be generalized as follows. Given a nonnegative data matrix X ∈ R n×p and a positive integer k min(n, p), find nonnegative matrices W ∈ R n×k and H ∈ R k×p to minimize a cost function in the form of some distance measure such as: The matrix product consists of a nonnegative basis matrix W ∈ R n×k and a nonnegative matrix of weights or coefficients H ∈ R k×p . The basis matrix W contains k basis column vectors, each of length n. These basis vectors or basis images contain the underlying features of the dataset X. Additive linear combinations of the basis images are obtained when taking the product of W and H because of the nonnegativity constraints. Each of the linear combinations represents or approximates a face in the data matrix X. It is intuitive to associate the process with combining individual parts to form a whole face.
The nonnegative matrix factorization algorithm was first proposed by Paatero and Tapper in 1994 under the name "Positive Matrix Factorization" (Paatero and Tapper [12]). Lee and Seung proposed an efficient multiplicative updating algorithm (Seung and Lee [16]) as well as using the Kullback-Leibler divergence as an alternative to the Euclidean distance for the cost function (Lee and Seung [10]). There are many published works which explore various cost functions on the matrix factorization (Cichocki et al. [3], Wang et al. [19], Hamza and Brady [7], and Sr and Dhillon [17], Xue et al. [22], Sandler and Lindenbaum [15]). Many different minimization methods for the solution of (2) have been explored for the purpose of decreasing the convergence time of Lee and Seung's iterative algorithm (Lin [11], Gonzalez and Zhang [6], Zdunek and Cichocki [23]). W and H are initialized with nonnegative random values in Lee and Seung's multiplicative iterative algorithm (Seung and Lee [16]). Various alternative initialization strategies for W and H have been proposed for the purpose of increasing the speed of convergence or to manipulate convergence to a specific desired result (Wild [20], Wild et al. [21], and Boutsidis and Gallopoulos [1]).
Various authors have adapted the NMF algorithm by applying auxiliary constraints to the matrix W and/or H. Often these constraints take the form of smoothness constraints (Piper et al. [14], Pauca et al. [13], and Chen and Cichocki [2]) or sparsity constraints (Hoyer [8], and Hoyer [9]). Recently a set of data-dependent auxiliary constraints was explored (Corsetti and Fokoué [4]). These types of auxiliary constraints are usually incorporated so as to take into account prior information about the application under examination or to guarantee desired characteristics in the solution for the W and H matrices. The secondary constraints are enforced through the use of penalty terms which extend the cost function of equation (2) as follows: For equation (3), J 1 (W) and J 1 (W) are the penalty terms and α and β (0 ≤ α ≤ 1 and 0 ≤ β ≤ 1) are the regularization parameters which serve to control the trade-off between the approximation error of WH in approximating X and the auxiliary constraints. This method is commonly referred to as "Constrained Nonnegative Matrix Factorization".
We propose a novel constrained NMF algorithm by incorporating a Toeplitz matrix in the penalty terms of equation (3). We refer to this algorithm as "Toeplitz Nonnegative Matrix Factorization" (TNMF). We compare the recognition performance of the TNMF algorithm with the recognition performance of the Zellner Nonnegative Matrix Factorization (ZNMF) algorithm (Corsetti and Fokoué [4]) which makes use of data-dependent penalties, unlike the TNMF algorithm. We also compare the recognition performance of the TNMF algorithm with several other constrained NMF algorithms (Pauca et al. [13], and Wang et al. [19]). We assess the recognition performance of the aforementioned algorithms using the Cambridge ORL Database of Faces as well as the Yale Database of Faces. We find that the ZNMF algorithm outperforms the constrained NMF algorithms for the ORL dataset simulations and the TNMF algorithm outperforms the other NMF algorithms for the Yale dataset simulations.

Constrained Nonnegative Matrix Factorization
Constrained Nonnegative Matrix Factorization extends the cost function of traditional NMF shown in (2) to that of (3). The functions J 1 (W) and J 2 (H) represent penalty terms that are meant to constrain the solution of (3). α and β are the respective regularization parameters of J 1 (W) and J 2 (H) such that 0 ≤ α ≤ 1 and 0 ≤ β ≤ 1. In accordance with (Pauca et al. [13]) we set: and We enforce smoothness in the basis matrix W and statistical sparseness (Hoyer [8]) in the weights matrix H by setting J 1 (W) and J 2 (H) equal to the square of their respective Frobenius norms (Pauca et al. [13]). Using the penalties shown in (4) and (5), the standard NMF multiplicative updating equations for W and H (Seung and Lee [16]) are modified as follows: and where t denotes the iteration.

Zellner Nonnegative Matrix Factorization
The inspiration for the ZNMF algorithm and its details are described in (Corsetti and Fokoué [4]).
The ZNMF algorithm incorporates Zellner's g-prior (Zellner [24]) and alters the objective function of equation 3 by setting: and where g = max(n, p 2 ).
Consequently, ∂ and ∂ For the ZNMF algorithm, the updating equations for W and H are: and

Toeplitz Nonnegative Matrix Factorization
Tipping [18] demonstrated the possibility of deriving sparse representations in kernel regression via suitably specified Gamma hyperpriors on the independent precisions of a Gaussian prior on the weights of the kernel expansion. Fokoué [5] explored a modified version of Tipping [18] by using structured matrix of the form In this paper, we adopt a different approach that seeks to achieve sparsity by directly exploiting the properties of Toeplitz type structured matrices. We argue that our approach makes sense for both variable selection in linear models and atom selection in kernel methods, because all our proposed matrices are reminiscent of matrices encountered in the analysis of autoregressive time series models. Indeed, such matrices do inherently capture correlations of varying degrees and can therefore isolate variables or atoms that are more dominant, leaving the least dominant ones as secondary members of a group. In a sense, our selected features are somewhat like representatives of a group with which the other members have a strong correlation.
We specify a Gaussian prior for w with a variance-matrix that is structuredà la Toeplitz, where c is constant.
This can be substantially improved upon by using This new variance-matrix structure has the inherent property of creating a banded matrix so that associations are gradually lessened.

Experimental Results
Simulations were carried out to compare the facial recognition performances of the CNMF, In an effort to improve computational efficiency, the resolutions of the ORL images were reduced from 112 × 92 to 28 × 23 in accordance with Wang et al. [19], which found that reducing the image resolution to 25% the original size did not have a substantial impact on the recognition performance of the algorithms. For each of the ORL simulations, the training dataset X 644×200   The effects on the facial recognition performance of the ρ parameter and the g-Prior parameter in the TNMF and ZNMF algorithms respectively were investigated in great detail via extensive computer simulation, as were the α and β parameters. The α and β parameters were constrained via the following relationship: such that 0 ≤ α ≤ 1 and 0 ≤ β ≤ 1. The optimal α and β parameter settings for the CNMF algorithm were obtained by searching across a space from 0 to 1 in increments of 0.01. The results were smoothed using a loess curve with a 0.50 degree of smoothing parameter. The smoothed results are displayed in Figure 3. The large point along each of the factorization rank lines denotes the point at which the maximum recognition performance occurs for that specific factorization rank.
The initial search space for the optimal α, β and g-prior parameter settings of the ZNMF algorithm, using the ORL dataset was quite vast and not particularly granular. In this initial search space, a factorization rank of k = 16 was selected. The g-prior parameter was searched across an interval from 100 to 10,000 in increments of 100; while the α parameter was explored across an interval from 0 to 1 in increments of 0.01. As stated previously, 25 replications were carried out at each of these unique parameter settings. The resulting surface is displayed in the top left of Figure 4. A promising region, defined by a g-prior less than 100 and α value between 0.20 and 0.80 is quite noticeable in the initial explorative surface. As a result, more granular parameter searches were carried out across the seven factorization ranks using values for the g-prior from 75 to 90 in increments of 0.50 and values of 0.20 to 0.80 in increments of 0.01 for α. The most promising surface was generated using k = 36 and is displayed in the top right of Figure 4. The optimal g-prior, α and β settings were 83, 0.44 and 0.56 respectively. A similar approach was used in finding the optimal settings for the α, β and g-prior parameters for the Yale dataset. The α parameter was explored over a space from 0 to 1 in increments of 0.02 while the g-prior parameter was explored over a space from 200 to 10,000 in increments of 50. Again, an initial, broad explorative surface was generated using a factorization rank of k = 16 and is provided in the lower left of Figure 4. A promising area of the initial broad surface is defined by a g-prior value between 3,500 and 4,500 and an α value between 0.01 and 0.30. Simulations were carried out within the aforementioned parameter subspace across the seven different factorization ranks. k = 100 was found to be the optimal setting for the factorization rank. The resulting surface is displayed in the bottom right of Figure 4. The optimal g-prior, α and β settings were 3500, 0.00 and 1.00, respectively. The ρ tuning parameter of the TNMF algorithm, as stated previously, was constrained to be 0 ≤ ρ ≤ 1; and as a result, granular performance surfaces were constructed in relatively little time for the ORL dataset. The α and ρ parameters were both explored over an interval from 0 to 1 in increments of 0.02 across all seven factorization ranks. The optimal surface was generated using a factorization rank of 25 and is displayed in the top of Figure 5. Optimal ρ, α and β settings were found to be 0.06, 0.68 and 0.32 respectively.
An initial search surface was generated for the Yale dataset using the TNMF algorithm. The  After identifying the optimal parameter settings in each of the aforementioned scenarios, 500 replications were carried out at each setting. The average recognition performances are shown in Figure 6 and parameter settings by algorithm and dataset are provided in Tables 1-3.  This implies that the ZNMF requires less information, in the form of lower factorization ranks, to produce equal and possibly greater recognition performance on the ORL database as other algorithms (Wang et al. [19]) produce when provided with more information in the form of higher factorization ranks. This is important for two related reasons: time and storage. A common problem for many nonnegative matrix factorization algorithms in which a large basis matrix is multiplied through with a large weights matrix is the often lengthy time with which it takes a computer to carry out the matrix multiplication. If a matrix factorization algorithm, such as ZNMF, can produce equally accurate results as other matrix factorization algorithms while using relatively lower dimensional basis and weights matrices then we might expect the ZNMF algorithm to take less time in producing its estimation of X depending on the complexity of the competing algorithms. Similarly, an algorithm that can produce equally impressive results as another algorithm while using substantially less storage (e.g. lower factorization ranks) may be beneficial.

Conclusion and Future Work
In this paper, we proposed the TNMF algorithm for the assessment of facial recognition and evaluated its capabilities in this regard using both the Cambridge ORL Database of Faces and the Yale Database of Faces across seven different factorization ranks. We compared the facial recognition capabilities of TNMF with a constrained version of the nonnegative matrix algorithm (CNMF) which imposes auxiliary penalties on the solution of (2) and also a second constrained version of nonnegative matrix factorization (ZNMF) which incorporates datadependent penalties into its auxiliary constraints. We found the ZNMF algorithm outperformed both TNMF and CNMF across all factorization ranks for the ORL dataset and achieved the highest average recognition rate of 90.97% at a factorization rank of 36. We found that TNMF and CNMF compared relatively similarly with respect to their recognition performances when used on the Yale Dataset and also that ZNMF drastically underperformed when compared with the other two algorithms across all factorization ranks for the Yale dataset. We found the TNMF algorithm achieved the highest average recognition rate (86.47%) for the Yale dataset at a factorization rank of 81.
Though our new TNMF algorithm does not impose data-dependent auxiliary constraints, we hope to apply other data-dependent constraints to the nonnegative matrix factorization algorithm. One such possibility would be to use G 1 (W) = trace(X T WW T X) where X T W ∈ R n×k , and G 2 (H) = trace(XH T HX T ) where XH T ∈ R p×k . Note that X T WW T X is n × n and is essentially the linear gram matrix of the projected X. XH T HX T is p × p and resembles the covariance matrix in the input space.
Nonnegative matrix factorization is applicable to a variety of tasks and therefore we also hope to move beyond facial recognition tasks and assess the performance of our collection of algorithms perhaps in text mining, social network analysis or Bioinformatics, specifically for the analysis of microarray data.