Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G ...Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.展开更多
Let G be a graph and f an integer-valued function defined on V(G). It is proved that every (0,mf - m+1)-graph G has a (0,f)-factorization orthogonal to any given subgraph with m edges.
Let G be a graph, k(1), ... , k(m) be positive integers. If the edges of graph G can be decomposed into some edge disjoint [0, k(1)]-factor F-1, ..., [0, k(m)]-factor F-m, then we can say (F) over bar = {F-1, ..., F-m...Let G be a graph, k(1), ... , k(m) be positive integers. If the edges of graph G can be decomposed into some edge disjoint [0, k(1)]-factor F-1, ..., [0, k(m)]-factor F-m, then we can say (F) over bar = {F-1, ..., F-m}, is a [0, k(i)](1)(m) -factorization of G. If H is a subgraph with m edges in graph G and / E (H) boolean AND E(F-i) / = 1 for all 1 less than or equal to i less than or equal to m, then we can call that (F) over bar is orthogonal to H. It is proved that if G is a [0, k(1) + ... + k(m) - m + 1]-graph, H is a subgraph with m edges in G, then graph G has a [0, k(i)](1)(m)-factorization orthogonal to H.展开更多
Orthogonal nonnegative matrix factorization(ONMF)is widely used in blind image separation problem,document classification,and human face recognition.The model of ONMF can be efficiently solved by the alternating direc...Orthogonal nonnegative matrix factorization(ONMF)is widely used in blind image separation problem,document classification,and human face recognition.The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method.When the given matrix is huge,the cost of computation and communication is too high.Therefore,ONMF becomes challenging in the large-scale setting.The random projection is an efficient method of dimensionality reduction.In this paper,we apply the random projection to ONMF and propose two randomized algorithms.Numerical experiments show that our proposed algorithms perform well on both simulated and real data.展开更多
Let m,t,r and k_(i)(1≤i≤m)be positive integers with k_(i)≥(t+3)r/2,and G be a digraph with vertex set V(G)and arc set E(G).Let H_(1),H_(2),…,H_(t) be t vertex-disjoint subdigraphs of G with mr arcs.In this article...Let m,t,r and k_(i)(1≤i≤m)be positive integers with k_(i)≥(t+3)r/2,and G be a digraph with vertex set V(G)and arc set E(G).Let H_(1),H_(2),…,H_(t) be t vertex-disjoint subdigraphs of G with mr arcs.In this article,it is verified that every[0,k_(1)+k_(2)+…+k_(m)-(m-1)r]-digraph G has a[0,k_(i)]_(1)^(m)-factorization r-orthogonal to every H_(i) for 1≤i≤t.展开更多
Let G be a graph with vertex set V（G） and edge set E（G）, and let g and f be two integer- valued functions defined on V（G） such that g（x）≤f（x） for all x ∈ V（G）. Then a （g, f）-factor of G is a spanning s...Let G be a graph with vertex set V（G） and edge set E（G）, and let g and f be two integer- valued functions defined on V（G） such that g（x）≤f（x） for all x ∈ V（G）. Then a （g, f）-factor of G is a spanning subgraph H of G such that g（x）≤d<sub>H</sub>（x）≤f（x） for all x ∈ V（G）. A （g, f）-factorization of G is a partition of E（G） into edge-disjoint （g,f）-factors. Let F={F<sub>1</sub>, F<sub>2</sub>...., F<sub>m</sub>} be a factorization of G, and H be a subgraph of G with mr edges. If F<sub>i</sub>. 1≤i≤m, has exactly r edges in common with H. then F is said to be r-orthogonal to H. In this paper it is proved that every （mg+kr, mf-kr）-graph. where m, k and r are positive integers with k【m and g≥r, contains a subgraph R such that R has a （g, f）-factorization which is r-orthogonal to a given subgraph H with kr edges.展开更多
The orthogonal nonnegative matrix factorization （ONMF） has many applications in a variety of areas such as data mining, information processing and pattern recognition. In this paper, we propose a novel initializatio...The orthogonal nonnegative matrix factorization （ONMF） has many applications in a variety of areas such as data mining, information processing and pattern recognition. In this paper, we propose a novel initialization method for the ONMF based on the Lanczos bidiagonalization and the nonnegative approximation of rank one matrix. Numerical experiments are given to show that our initialization strategy is effective and efficient.展开更多
The restrictively preconditioned conjugate gradient （RPCG） method is further developed to solve large sparse system of linear equations of a block two-by-two structure. The basic idea of this new approach is that we...The restrictively preconditioned conjugate gradient （RPCG） method is further developed to solve large sparse system of linear equations of a block two-by-two structure. The basic idea of this new approach is that we apply the RPCG method to the normal-residual equation of the block two-by-two linear system and construct each required approximate matrix by making use of the incomplete orthogonal factorization of the involved matrix blocks. Numerical experiments show that the new method, called the restrictively preconditioned conjugate gradient on normal residual （RPCGNR）, is more robust and effective than either the known RPCG method or the standard conjugate gradient on normal residual （CGNR） method when being used for solving the large sparse saddle point problems.展开更多
基金This work was supported by NNSF. RFDP and NNSF of shandong province(Z2000A02 ).
文摘Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.
文摘Let G be a graph and f an integer-valued function defined on V(G). It is proved that every (0,mf - m+1)-graph G has a (0,f)-factorization orthogonal to any given subgraph with m edges.
文摘Let G be a graph, k(1), ... , k(m) be positive integers. If the edges of graph G can be decomposed into some edge disjoint [0, k(1)]-factor F-1, ..., [0, k(m)]-factor F-m, then we can say (F) over bar = {F-1, ..., F-m}, is a [0, k(i)](1)(m) -factorization of G. If H is a subgraph with m edges in graph G and / E (H) boolean AND E(F-i) / = 1 for all 1 less than or equal to i less than or equal to m, then we can call that (F) over bar is orthogonal to H. It is proved that if G is a [0, k(1) + ... + k(m) - m + 1]-graph, H is a subgraph with m edges in G, then graph G has a [0, k(i)](1)(m)-factorization orthogonal to H.
基金the National Natural Science Foundation of China(No.11901359)Shandong Provincial Natural Science Foundation(No.ZR2019QA017)。
文摘Orthogonal nonnegative matrix factorization(ONMF)is widely used in blind image separation problem,document classification,and human face recognition.The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method.When the given matrix is huge,the cost of computation and communication is too high.Therefore,ONMF becomes challenging in the large-scale setting.The random projection is an efficient method of dimensionality reduction.In this paper,we apply the random projection to ONMF and propose two randomized algorithms.Numerical experiments show that our proposed algorithms perform well on both simulated and real data.
文摘Let m,t,r and k_(i)(1≤i≤m)be positive integers with k_(i)≥(t+3)r/2,and G be a digraph with vertex set V(G)and arc set E(G).Let H_(1),H_(2),…,H_(t) be t vertex-disjoint subdigraphs of G with mr arcs.In this article,it is verified that every[0,k_(1)+k_(2)+…+k_(m)-(m-1)r]-digraph G has a[0,k_(i)]_(1)^(m)-factorization r-orthogonal to every H_(i) for 1≤i≤t.
基金This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China
文摘Let G be a graph with vertex set V（G） and edge set E（G）, and let g and f be two integer- valued functions defined on V（G） such that g（x）≤f（x） for all x ∈ V（G）. Then a （g, f）-factor of G is a spanning subgraph H of G such that g（x）≤d<sub>H</sub>（x）≤f（x） for all x ∈ V（G）. A （g, f）-factorization of G is a partition of E（G） into edge-disjoint （g,f）-factors. Let F={F<sub>1</sub>, F<sub>2</sub>...., F<sub>m</sub>} be a factorization of G, and H be a subgraph of G with mr edges. If F<sub>i</sub>. 1≤i≤m, has exactly r edges in common with H. then F is said to be r-orthogonal to H. In this paper it is proved that every （mg+kr, mf-kr）-graph. where m, k and r are positive integers with k【m and g≥r, contains a subgraph R such that R has a （g, f）-factorization which is r-orthogonal to a given subgraph H with kr edges.
基金Acknowledgments. The work is supported by National Natural Science Foundation of China No. 10961010.
文摘The orthogonal nonnegative matrix factorization （ONMF） has many applications in a variety of areas such as data mining, information processing and pattern recognition. In this paper, we propose a novel initialization method for the ONMF based on the Lanczos bidiagonalization and the nonnegative approximation of rank one matrix. Numerical experiments are given to show that our initialization strategy is effective and efficient.
基金supported by the National Basic Research Program (No.2005CB321702)the China NNSF Outstanding Young Scientist Foundation (No.10525102)the National Natural Science Foundation (No.10471146),P.R.China
文摘The restrictively preconditioned conjugate gradient （RPCG） method is further developed to solve large sparse system of linear equations of a block two-by-two structure. The basic idea of this new approach is that we apply the RPCG method to the normal-residual equation of the block two-by-two linear system and construct each required approximate matrix by making use of the incomplete orthogonal factorization of the involved matrix blocks. Numerical experiments show that the new method, called the restrictively preconditioned conjugate gradient on normal residual （RPCGNR）, is more robust and effective than either the known RPCG method or the standard conjugate gradient on normal residual （CGNR） method when being used for solving the large sparse saddle point problems.
