JP6721533B2 - Graphical lasso computing device, graphical lasso computing method and graphical lasso computing program - Google Patents

Description

The present invention relates to a graphical lasso computing device, a graphical lasso computing method, and a graphical lasso computing program.

Graphical lasso is one of the most famous methods for calculating an invalid graph from multidimensional data using L ₁ regularization (see Non-Patent Document 1). Here, the node of the graph corresponds to each data point of the multidimensional data, and the edge corresponds to the condition dependency between the data points.

The graphical lasso estimates the inverse matrix Θ (=Σ ⁻¹ ) of the covariance matrix Σ based on the multivariate Gaussian distribution with mean μ. If the (i,j) element of the matrix Θ is non-zero (θ[i,j]≠0), it means that the i-th and j-th variables have a conditional dependency. The graphical lasso uses the penalty of L ₁ when estimating the matrix Θ to make the structure sparse. When the matrix X is an N×P data matrix corresponding to P variables of N dimensions, the matrix S is such that S=X ^T X (the matrix X ^T is the transpose of the matrix X). If the covariance matrix is used, the graphical lasso estimates a sparse graph structure by maximizing the objective function shown in Expression (1) below.

In Expression (1), ρ is a positive L ₁ normalization parameter that determines the degree of sparseness of the estimated graph. Also, the problem of obtaining a sparse structure in this equation (1) becomes convex. The graphical lasso iteratively updates the lasso coefficients using the coordinate descent method to solve this problem. Specifically, the graphical lasso performs round-robin calculation until each row and each column of the matrix to be estimated converges.

Then, in order to reduce the calculation cost, Friedman et al. proposed a screening method (see Non-Patent Document 2, for example). This screening method limits the calculation for updating the coefficient to only the connected components, so that it is possible to effectively specify the variable for which the update is calculated. This screening method is the most known method for accelerating the graphical lasso.

Jerome Friedman, Trevor Hastie and Robert Tibshirani, “Sparse inverse covariance estimation with the graphical lasso”, Biostatistics, 9(3):432−441, 2008. Daniela M. Witten, Jerome H. Friedman and Noah Simon, “New Insights and Faster Computations for the Graphical Lasso”, Journal of Computational and Graphical Statistics, 20(4):892−900, 2011.

However, this screening method has a problem that all the elements of the covariance matrix must be calculated, and the calculation cost of the graphical lasso cannot be effectively reduced.

The present invention has been made in view of the above, and provides a graphical lasso calculation device, a graphical lasso calculation method, and a graphical lasso calculation program that can calculate a graphical lasso that calculates a sparse structure from multidimensional data at high speed. The purpose is to provide.

In order to solve the above-mentioned problems and achieve the object, a graphical lasso calculation device according to the present invention is a graphical lasso calculation device that calculates a sparse structure from multidimensional data, and is a singular matrix of an input multidimensional matrix. An SVD calculator that calculates SVD (Singular Value Decomposition), an approximate covariance calculator that calculates the approximate covariance between data points from the SVD, and data that may have edges due to the approximation. Set the covariance calculator that calculates the covariance between points, the connected part calculator that calculates the block that is the connected part of the adjacency matrix that consists of the covariance, and the component of the block for which the coefficient of lasso is to be calculated. An update component setting unit, a coefficient calculation unit that repeatedly calculates the first coefficient in lasso, and a non-update component confirmation unit that confirms whether or not the second coefficient in lasso is non-zero for the component to be calculated. , A first determination unit that determines whether or not to continue the iterative calculation for the first coefficient in the component to be calculated, according to the confirmation result of whether or not the second coefficient is non-zero, and all components A second determination unit for determining whether or not to continue the iterative calculation of.

According to the present invention, a graphical lasso that calculates a sparse structure from multidimensional data can be calculated at high speed.

FIG. 1 is a diagram showing how to obtain the coefficient in Expression (3). FIG. 2 is a block diagram showing an example of the main configuration of the graphical lasso calculation apparatus according to this embodiment. FIG. 3 is a diagram showing Definition 1. FIG. 4 is a diagram showing Definition 2. FIG. 5 is a diagram showing Lemma 1. FIG. 6 is a diagram showing Lemma 2. FIG. 7 is a diagram showing Lemma 3. FIG. 8 is a diagram showing an algorithm of the graphical lasso calculation process according to the embodiment. FIG. 9 is a flowchart showing the processing procedure of the graphical lasso calculation processing according to the embodiment. FIG. 10 is a diagram showing conditions for repeated calculation termination. FIG. 11 is a diagram showing Theorem 1. FIG. 12 is a diagram showing Theorem 2. FIG. 13 is a diagram illustrating an example of a computer that realizes a graphical lasso calculation device by executing a program.

Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings. The present invention is not limited to this embodiment. In the description of the drawings, the same parts are designated by the same reference numerals.

[Conventional graphical lasso calculation method]
First, a conventional graphical lasso calculation method will be described. Graphical lasso is a calculation method that calculates sparse structures from multidimensional data. For example, given an N×P data matrix X consisting of N observations and P variables, the graphical lasso maximizes the objective function of equation (1) to obtain a covariance from the matrix X. Estimate the inverse matrix Θ of the matrix Σ. When S is the actual covariance matrix and I is the unit matrix, the graphical lasso optimizes each row and column of the matrix W given as S=S+ρI using the coordinate descent method. Specifically, first, in the graphical lasso, the matrices W and S are divided as in the following Expression (2).

In the graphical lasso, the rows and columns of the iteration matrix W are rearranged so that the row and the column for calculating the lasso solution come last. Then, the following formula (3) is shown.

Note that the diagonal elements of the matrix W are unchanged in the iterative calculation. FIG. 1 is a diagram showing how to obtain the coefficient in Expression (3). As shown in FIG. 1, the coefficient in Expression (3) is obtained.

Here, in order to reduce the calculation cost, Friedman et al. proposed a screening method (see Non-Patent Document 2). This screening method is such that if |S[i,j]|≦ρ holds for all j-th variables where i≠j, then the i-th variable becomes an isolated node in the estimated graph. It is based on the knowledge. Therefore, in this screening method, when |S[i,j]|>ρ, an adjacency matrix of a graph in which a pair of nodes is connected by an edge is obtained, and a connected component of the graph is obtained. This screening method limits the calculation for updating the coefficient to only the connected components, so that it is possible to effectively specify the variable for which the update is calculated.

This screening method is the best known method for speeding up the graphical lasso. However, this method has a problem in that all the elements of the covariance matrix must be calculated and the calculation cost cannot be effectively reduced. In this case, letting T be the number of repeated calculations in each row and column of the matrix Σ and B be the number of non-zero components in each row and column of the estimated graph, the computational cost required for the graphical lasso is O(NP ² +PBT).

[Outline of Embodiment]
According to the method used in this embodiment, the graphical lasso can be calculated at higher speed. First, an outline of the calculation method according to the present embodiment will be described, and then the details of the calculation method according to the present embodiment will be described. It should be noted that the symbols indicating the respective sets are indicated by uppercase letters in the specification in the specification, and by a font style in which the uppercase letters are omitted in the drawings.

As described above, in the conventional method, in order to reduce the number of coefficients updated in each iterative calculation, each element of the covariance matrix S is calculated, and if |S[i,j]|>ρ, the edge is calculated. To add. This indicates that in the existing method, all elements of the matrix S must be calculated in order to calculate the continuous component. Furthermore, in the conventional method, due to the property of lasso, all the coefficients are calculated as round robin even though the values of almost all the coefficients become zero.

On the other hand, in the present embodiment, in order to perform the calculation at high speed, the SVD is used to approximate the covariance S[i,j], and the upper limit value and the lower limit value thereof are calculated at high speed.

Then, in the present embodiment, an accurate value of covariance is calculated when it is determined that covariance may have an edge by approximation. In other words, in the present embodiment, in the matrix estimated using SVD, a block having a non-zero component is obtained at high speed before starting repeated calculation. In addition, in the present embodiment, a component expected to have a non-zero element is selected and repeatedly updated. In other words, in the present embodiment, non-zero components in the estimated matrix are selectively updated.

As described above, in the present embodiment, an accurate covariance value is calculated only when it is determined that the covariance may have an edge by approximation, and only a small number of connected components are repeatedly updated. To do. Therefore, according to the present embodiment, the number of repetitive calculations can be reduced as compared with the conventional method, and thus the graphical lasso can be calculated at high speed.

[Configuration of Embodiment]
First, the configuration of the graphical lasso calculation apparatus according to the embodiment will be described with reference to FIG. FIG. 2 is a block diagram showing an example of the main configuration of the graphical lasso calculation apparatus according to this embodiment. As shown in FIG. 2, the graphical lasso calculation device 1 includes an SVD calculation unit 11, an approximate covariance calculation unit 12, a covariance calculation unit 13, a connected portion calculation unit 14, an update component setting unit 15, a coefficient calculation unit 16, An update component confirmation unit 17, an iterative calculation determination unit 18 (first determination unit), a convergence determination unit 19, and an inverse matrix calculation unit 20 are included.

The SVD calculator 11 calculates the SVD of the input multidimensional matrix. The approximate covariance calculation unit 12 calculates the covariance between data points when there is a possibility of having an edge due to the approximation. The covariance calculation unit 13 calculates the covariance between data points when there is a possibility of having edges due to approximation. The connected part calculator 14 calculates a block that is a connected part of an adjacency matrix composed of covariances.

The update component setting unit 15 sets the component of the coefficient to be calculated in lasso among the blocks. The coefficient calculation unit 16 repeatedly calculates the first coefficient in lasso for the component to be calculated. The first coefficient is a column vector that is the i-th element of the second coefficient described later. The non-updated component confirmation unit 17 confirms whether or not the second coefficient in lasso is non-zero. The second coefficient is the coefficient of the i-th lasso corresponding to the i-th (i is an arbitrary number) column of the adjacency matrix.

The iterative calculation determination unit 18 (first determination unit) determines whether or not to continue the iterative calculation for the first coefficient in the component to be calculated according to the confirmation result of whether or not the second coefficient is nonzero. Determine whether. The iterative calculation determination unit 18 determines not to continue the iterative calculation for the first coefficient when the second coefficient in lasso is not non-zero. The convergence determination unit 19 (second determination unit) determines whether or not to continue the iterative calculation of all components. The inverse matrix calculation unit 20 calculates the inverse matrix Θ of the covariance matrix Σ.

[Approximate covariance calculation processing]
Here, the approximate covariance calculator 12 approximates the covariance by SVD to calculate the upper limit value and the lower limit value of the covariance. Therefore, an approximate covariance calculation process by the approximate covariance calculation unit 12, that is, a method by which the approximate covariance calculation unit 12 obtains the upper limit value and the lower limit value of the covariance S[i,j] will be described.

In this method, an N×P data matrix is approximated by a matrix of rank n (n<<N) by SVD. SVD is an orthogonal transform and has high accuracy in terms of squared error. FIG. 3 is a diagram showing Definition 1. FIG. 4 is a diagram showing Definition 2. Definitions 1 and 2 are necessary for the approximate covariance calculation process. The approximate covariance calculation unit 12 obtains the upper limit value of the covariance S[i,j] using the method shown in FIG. Here, before the iterative calculation is started, the column vector L ₂ can be obtained at a calculation cost of O(NP). Similarly, the SVD of the matrix X can be obtained at a calculation cost of O(NPlogn) (for details, see Non-Patent Document 1).

Then, the approximate covariance calculation unit 12 obtains the lower limit value of the covariance S[i,j] using the method shown in FIG. FIG. 5 is a diagram showing Lemma 1. The relation shown in Lemma 1 shown in FIG. 5 holds for the upper and lower limits of the covariance S[i,j] (for details, see Nathan Halko, Per-Gunnar Martinsson and Joel A. Tropp, “FINDING STRUCTURE WITH RANDOMNESS: (See PROBABILISTIC ALGORITHMS FOR CONSTRUCTING APPROXIMATE MATRIX DECOMPOSITIONS”, SIAM Review, 53(2):217-288, 2011.)

From the viewpoint of the amount of calculation, if L ₂ and SVD of each column vector of the matrix X have been calculated, the costs required to calculate the upper limit value and the lower limit value are shown in FIGS. 3 and 4. From definitions 1 and 2, it becomes O(n).

[Covariance calculation processing]
Next, the covariance calculation processing by the covariance calculation unit 13 will be described. The covariance calculation unit 13 specifies whether or not there is a possibility of having an edge by using the upper limit value and the lower limit value of the covariance. Compute the covariance between data points. FIG. 6 is a diagram showing Lemma 2.

From Lemma 2, if the L ₁ normal parameter ρ is greater than or equal to the upper limit of covariance and −ρ is less than or equal to the lower limit of covariance, then this pair of nodes has no edges in the adjacency matrix. That is, if ρ is less than the upper limit of covariance and −ρ is greater than the lower limit of covariance, then this pair of nodes may have edges in the adjacency matrix.

In the present embodiment, the covariance calculation unit 13 determines that there is a possibility of having an edge by approximation, that is, ρ is less than the upper limit of covariance and −ρ is greater than the lower limit of covariance. Only compute the covariance between the data points. Therefore, the covariance calculation unit 13 can quickly calculate the adjacency matrix in the screening method by using the upper limit value and the lower limit value of the covariance from the property shown in Lemma 2 of FIG.

[Repeated calculation processing]
Next, the iterative calculation process according to the embodiment will be described. In the embodiment, in order to calculate the graphical lasso at high speed, the coefficient calculation unit 16 calculates the first coefficient in the lasso expected to be non-zero until it selectively converges. For the first coefficient not selected by the coefficient calculation unit 16, the non-updated component confirmation unit 17 confirms whether or not it has a non-zero coefficient after the repeated calculation.

In this process, if |S[i,j]|>ρ holds, the (i,j) element of the inverse matrix Θ is expected to have a nonzero value, and the corresponding lasso coefficient also becomes nonzero. It is based on the finding that it is likely. A block of connected components comprising the i-th variable resulting B _i from techniques by screening a set of set B _i B _i = | When set as a _{{j B j = B i}} , technique by screening Then, the i-th coefficient is calculated using the set B _i −i. On the other hand, in the present embodiment, the coefficient calculation unit 16 uses Equation (3) until the coefficients for the i-th variable are converged using the set U _i initialized as Equation (4) below. Calculate.

Here, it is clear that the relationship is the set U _i ⊆ set B _i . Then, the set U _i can be obtained at high speed by using the upper limit value and the lower limit value.

Also, let U _i ′ be a set as in the following expression (5).

The non-updated component confirmation unit 17 confirms after repeated calculation whether the coefficients included in the set U _i ′ have non-zero coefficients. As a result, in the present embodiment, in order to calculate the i-th coefficient, the set U _i +the set U _i ′=the set B _i −i, so the i-th coefficient is calculated using the set B _i −i. The same results can be obtained as with the computational screening method. FIG. 7 is a diagram showing Lemma 3. The present embodiment is theoretically based on the property of Lemma 3.

Whereas the conventional screening method updates the coefficients included in the set B _i to Land Robin, the lemma 3 is that the present embodiment confirms the coefficients included in the set U _i ′ to obtain the result of estimation. It is shown that the coefficients included in the set U _i (set U _i ⊆ set B _i ) can be selectively updated without affecting the.

In the present embodiment, the coefficients included in the set U _i are repeatedly updated, but the coefficients included in the set U _i ′ are not repeatedly calculated. As a result, according to the present embodiment, since the coefficients are selectively converged, high speed processing is possible. In the present embodiment, the non-updated components check unit 17 _'checks whether contains nonzero coefficients in the set U _i' set U _i contains nonzero coefficients in If so, add the coefficient to the set U _i . Then, the coefficients are recursively converged, and the processing is performed for all i such that iε set U _i ′ until the following expression (6) is satisfied.

[Processing procedure for graphical lasso calculation]
The processing procedure of the graphical lasso calculation processing according to the embodiment will be described with reference to FIGS. 8 and 9. FIG. 8 is a diagram showing an algorithm of the graphical lasso calculation process according to the embodiment. FIG. 9 is a flowchart showing the processing procedure of the graphical lasso calculation processing according to the embodiment.

In Algorithm 1 shown in FIG. 8, matrix A is a P×P adjacency matrix, and m is the number of blocks of connected components obtained by the screening method. Then, in the graphical lasso calculation process according to the present embodiment, the blocks are processed one by one. Further, the matrix S ⁽ⁱ⁾ , the matrix W ⁽ⁱ⁾ , the unit matrix I ⁽ⁱ⁾ , the vectors w ⁽ⁱ⁾ ₁₂ , w ⁽ⁱ⁾ ₁₁ , and the inverse matrix Θ ⁽ⁱ⁾ are matrices corresponding to the blocks of i, respectively. S, matrix W, unit matrix I, vectors w ₁₂ , w ₁₁ , and inverse matrix Θ.

In the present embodiment, first, the SVD calculation unit 11 calculates the SVD of the data matrix X and initializes the adjacency matrix A (the first and second rows of the algorithm shown in FIG. 8 and steps S1 and S2 shown in FIG. 9). ). Subsequently, in order to obtain the edge of the adjacency matrix at high speed, the approximate covariance calculation unit 12 calculates the upper limit value and the lower limit value of the covariance of the matrix S, and if these satisfy the condition for the edge of Lemma 2. The covariance calculation unit 13 calculates an accurate value of covariance (algorithms 3 to 9 in FIG. 8, steps S3 to S11 in FIG. 9).

Then, the connected part calculation unit 14 calculates a block of connected components from the matrix A (10th line in the algorithm shown in FIG. 8, step S12 in FIG. 9). When the update component setting unit 15 sets the blocks 1 to m that are the coefficient calculation targets in lasso (the 11th line in the algorithm shown in FIG. 8, step S13 in FIG. 9), the coefficient calculation unit 16 sets First, the matrix S( ⁱ ) and the matrix W( ⁱ ) are calculated (algorithm lines 12 to 13 shown in FIG. 8, steps S14 and S15 in FIG. 9). Then, the coefficient calculation unit 16 calculates the iterative coefficient using the set U _j until it converges (the 15th to 18th lines of the algorithm shown in FIG. 8, steps S16 to S18 in FIG. 9).

FIG. 10 is a diagram showing conditions for repeated calculation termination. Based on Lemma 3, the non-updated component confirmation unit 17 confirms whether or not the second coefficient in lasso is non-zero, and if it is determined that the relationship shown in FIG. Cancels the iterative calculation (algorithms 19 to 24 in FIG. 8, steps S19 to S25 in FIG. 9).

Then, the update component setting unit 15 updates the matrix W( ⁱ ) after the iterative calculation (the 25th line of the algorithm shown in FIG. 8, step S26 shown in FIG. 9). Subsequently, the convergence determination unit 19 determines whether or not the matrix W( ⁱ ) converges (step S27 shown in FIG. 9).

When the convergence determination unit 19 does not determine that the matrix W( ⁱ ) converges (step S27: No shown in FIG. 9), these processes (algorithms 11 to 25th line shown in FIG. 8, steps shown in FIG. 9). S13 to S25) are performed (the 26th line of the algorithm shown in FIG. 8).

Then, when the convergence determination unit 19 determines that the matrix W( ⁱ ) converges (step S27: Yes shown in FIG. 9), the inverse matrix calculation unit 20 calculates the inverse matrix Θ( ⁱ from the matrix W( ⁱ ). ) Is calculated (the 27th line of the algorithm shown in FIG. 8, step S28 shown in FIG. 9), the calculated inverse matrix Θ( ⁱ ) is output (step S29 shown in FIG. 9), and the graphical lasso calculation process ends. ..

Then, for the above Algorithm 1, the properties shown in Theorems 1 and 2 hold. FIG. 11 is a diagram showing Theorem 1. FIG. 12 is a diagram showing Theorem 2.

[Effects of this Embodiment]
As described above, in this embodiment, an accurate covariance value is calculated only when it is determined that the covariance may have an edge by approximation, and the connected component has a small number of non-zero elements. Only the expected components are updated repeatedly. Therefore, according to the present embodiment, the number of repetitive calculations can be reduced as compared with the conventional method, and thus the graphical lasso can be calculated at high speed.

[System configuration of the embodiment]
Each component of the graphical lasso calculation device 1 shown in FIG. 1 is functionally conceptual, and does not necessarily have to be physically configured as illustrated. That is, the specific form of the distribution and integration of the functions of the graphical lasso computing device 1 is not limited to the one shown in the figure, and all or part of the functional or functional units may be used in arbitrary units according to various loads and usage conditions. It can be physically distributed or integrated.

Further, each processing performed in the graphical lasso computing device 1 is realized by a CPU (Central Processing Unit), a GPU (Graphics Processing Unit), and a program that is analyzed and executed by the CPU and the GPU. May be done. Further, each processing performed in the graphical lasso calculation device 1 may be realized as hardware by a wired logic.

Further, of the processes described in the embodiments, all or part of the processes described as being automatically performed can be manually performed. Alternatively, all or part of the processing described as being manually performed can be automatically performed by a known method. In addition, the processing procedure, control procedure, specific name, and information including various data and parameters described above and illustrated can be appropriately changed unless otherwise specified.

[program]
FIG. 13 is a diagram illustrating an example of a computer in which the graphical lasso calculation device 1 is realized by executing a program. The computer 1000 has, for example, a memory 1010 and a CPU 1020. The computer 1000 also has a hard disk drive interface 1030, a disk drive interface 1040, a serial port interface 1050, a video adapter 1060, and a network interface 1070. These units are connected by a bus 1080.

The memory 1010 includes a ROM (Read Only Memory) 1011 and a RAM 1012. The ROM 1011 stores, for example, a boot program such as a BIOS (Basic Input Output System). The hard disk drive interface 1030 is connected to the hard disk drive 1090. The disk drive interface 1040 is connected to the disk drive 1100. For example, a removable storage medium such as a magnetic disk or an optical disk is inserted into the disk drive 1100. The serial port interface 1050 is connected to, for example, a mouse 1110 and a keyboard 1120. The video adapter 1060 is connected to the display 1130, for example.

The hard disk drive 1090 stores, for example, an OS 1091, an application program 1092, a program module 1093, and program data 1094. That is, the program defining each process of the graphical lasso computing device 1 is implemented as the program module 1093 in which the code executable by the computer 1000 is described. The program module 1093 is stored in the hard disk drive 1090, for example. For example, the hard disk drive 1090 stores a program module 1093 for executing the same processing as the functional configuration of the graphical lasso computing device 1. The hard disk drive 1090 may be replaced with an SSD (Solid State Drive).

Further, the setting data used in the processing of the above-described embodiment is stored as the program data 1094 in, for example, the memory 1010 or the hard disk drive 1090. Then, the CPU 1020 reads out the program module 1093 and the program data 1094 stored in the memory 1010 or the hard disk drive 1090 to the RAM 1012 as necessary and executes them.

The program module 1093 and the program data 1094 are not limited to being stored in the hard disk drive 1090, but may be stored in, for example, a removable storage medium and read by the CPU 1020 via the disk drive 1100 or the like. Alternatively, the program module 1093 and the program data 1094 may be stored in another computer connected via a network (LAN, WAN, etc.). Then, the program module 1093 and the program data 1094 may be read by the CPU 1020 from another computer via the network interface 1070.

The embodiments to which the invention made by the present inventor is applied have been described above, but the present invention is not limited to the description and the drawings, which form a part of the disclosure of the present invention according to the present embodiment. That is, all other embodiments, examples, operation techniques and the like made by those skilled in the art based on the present embodiment are included in the scope of the present invention.

1 graphical lasso calculation device 11 SVD calculation unit 12 approximate covariance calculation unit 13 covariance calculation unit 14 connected part calculation unit 15 update component setting unit 16 coefficient calculation unit 17 non-updated component confirmation unit 18 iterative calculation determination unit 19 convergence determination unit 20 Inverse matrix calculator

Claims (6)

A graphical lasso computing device for computing a sparse structure from multidimensional data,
An SVD calculator that calculates a Singular Value Decomposition (SVD) of the input multidimensional matrix,
An approximate covariance calculator that calculates the approximate covariance between data points from SVD,
A covariance calculator that calculates the covariance between data points when there is a possibility of having edges due to approximation,
A connected part calculator that calculates a block that is the connected part of an adjacency matrix consisting of covariances,
Of the blocks, an update component setting unit that sets a component of a coefficient calculation target in lasso,
A coefficient calculation unit that repeatedly calculates a first coefficient in lasso in the component to be calculated;
a non-updated component confirmation unit that confirms whether or not the second coefficient in lasso is non-zero;
A first determination unit that determines whether or not to continue the iterative calculation for the first coefficient in the component to be calculated, according to the confirmation result of whether or not the second coefficient is non-zero;
A second determination unit that determines whether or not to continue the iterative calculation of all components;
And a graphical lasso computing device. The approximate covariance calculation unit performs an approximation of covariance by SVD to calculate an upper limit value and a lower limit value of the covariance,
The graphical lasso calculation apparatus according to claim 1, wherein the covariance calculation unit uses the upper limit value and the lower limit value of the covariance to identify the presence or absence of the possibility of having the edge. The second coefficient is the coefficient of the i-th lasso corresponding to the i-th (i is an arbitrary number) column of the component to be calculated,
3. The graphical lasso calculation device according to claim 1, wherein the first coefficient is a column vector which is an i-th element of the second coefficient. The first determination unit determines that the iterative calculation for the first coefficient is not continued when the second coefficient is non-zero, and the first determination unit determines when the second coefficient is non-zero. 4. The graphical lasso calculation device according to claim 1, wherein it is determined that the iterative calculation for the coefficient is continued. A graphical lasso calculation method executed by a graphical lasso calculation device that calculates a sparse structure from multidimensional data,
An SVD calculation step for calculating the SVD of the input multidimensional matrix,
An approximate covariance calculation step of calculating an approximate covariance between data points from SVD,
A covariance calculation step of calculating a covariance between data points when there is a possibility that the approximation has edges.
A connected part calculation step of calculating a block that is a connected part of an adjacency matrix composed of covariance,
Of the blocks, an update component setting step of setting a component of a coefficient calculation target in lasso,
A coefficient calculation step of repeatedly calculating a first coefficient in lasso in the component to be calculated;
a non-updated component confirmation step of confirming whether or not the second coefficient in lasso is non-zero,
A first determining step of determining whether or not to continue the iterative calculation for the first coefficient in the component to be calculated, in accordance with the confirmation result of whether or not the second coefficient is non-zero;
A second convergence determination step of determining whether or not to repeat the iterative calculation of all components;
A method of computing a graphical lasso, characterized by having. A graphical lasso calculation program for causing a computer to function as the graphical lasso calculation device according to claim 1.

Images