US2010082643A1PendingUtilityA1
Computer Implemented Method and Program for Fast Estimation of Matrix Characteristic Values
Est. expiryNov 30, 2025(expired)· nominal 20-yr term from priority
G06F 16/31
41
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A term-by-document (or part-by-collection) matrix can be used to index documents (or collections) for information retrieval applications. Reducing the rank of the indexing matrix can further reduce the complexity of information retrieval. A method for index matrix rank reduction can involve computing a singular value decomposition and then retaining singular values based on the singular values corresponding to singular values of multiple topics. The expected singular values corresponding to a topic can be determined using the roots of a specially formed characteristic polynomial. The coefficients of the special characteristic polynomial can be based on computing the determinants of a Gram matrix of term (or part) probabilities, a method of recursion, or a method of recursion further weighted by the probability of document (or collection) lengths.
Claims
exact text as granted — not AI-modified1 - 31 . (canceled)
32 . A program product including a computer readable computer program encoded in a storage medium, the computer program executing an algorithm for computing a characteristic value of a matrix, comprising steps of:
providing a first matrix; providing a probability model by sampling from the first matrix; and extrapolating from the probability model a characteristic value of the first matrix.
33 . The program product according to claim 32 , wherein the characteristic value is a singular value of the first matrix.
34 . The program product according to claim 32 , wherein the characteristic value is an eigenvalue of the first matrix.
35 . The program product according to claim 32 , wherein the probability model comprises:
a probability distribution corresponding to a set of elements; a probability distribution corresponding to a set of sample lengths; and a probability of a sample from the probability model.
36 . The program product according to claim 32 , wherein the step of extrapolating from the probability model comprises the steps of:
constructing a polynomial corresponding to the probability model; and extrapolating from the polynomial to obtain the characteristic value of the first matrix.
37 . The program product according to claim 36 , wherein the step of extrapolating from the polynomial comprises the steps of:
finding a root of the polynomial for the probability model of the first matrix; and extrapolating from the root of the polynomial to obtain the characteristic value of the first matrix.
38 . The program product according to claim 37 , wherein the step of extrapolating from the root of the polynomial comprises the steps of:
multiplying the root by an expected number of samples from the probability model; and taking the square root of the resulting value to obtain the characteristic value.
39 . The program product according to claim 36 , wherein the step of constructing the polynomial comprises the steps of:
computing one or more coefficients c i ; and dividing each computed coefficient c i by i! to obtain the polynomial
λ
t
-
c
1
1
!
λ
t
-
1
+
c
2
2
!
λ
t
-
2
-
⋯
±
c
t
t
!
λ
0
wherein each of the non-computed coefficients is set to zero and t is from the probability model.
40 . The program product according to claim 39 , wherein the step of computing a coefficient c i of the polynomial comprises computing a probabilistically weighted value
c
i
=
∑
l
c
i
(
l
)
prob
(
l
)
comprising an additional coefficient c i (l) corresponding to a length l and probability prob(l) from the probability model to obtain the coefficient c i .
41 . The program product according to claim 40 , wherein the step of computing the coefficient c i (l) of the polynomial for the length l comprises computing a determinant of a Gram matrix |B i T B i |, wherein B i is a matrix whose i columns are i copies of a column vector of probabilities from the probability model that depend on l, to obtain the coefficient c i (l).
42 . The program product according to claim 40 , wherein the step of computing the coefficient c i (l) of the polynomial for the length l comprises using a recursive formula to obtain the coefficient c i (l).
43 . The program product according to claim 42 , wherein the recursive formula comprises
c
n
+
1
(
l
)
=
∑
j
=
0
n
(
n
j
)
(
-
1
)
j
(
j
!
)
a
j
+
1
c
n
-
j
(
l
)
based on the length l, coefficients c n−j (l) with c 0 (l)=1, and traces of powers of a second matrix M wherein a n =trace(M n ).
44 . The program product according to claim 43 , wherein the second matrix M comprises expected values of products of pairs of probabilities according to the corresponding length l from the probability model.
45 . The program product according to claim 43 , wherein the second matrix M comprises
M
ij
=
{
1
-
(
1
-
p
i
)
l
,
i
=
j
1
-
(
1
-
p
i
)
l
-
(
1
-
p
j
)
l
-
(
1
-
p
i
-
p
j
)
l
,
i
≠
j
wherein p i and p j and l are from the probability model.
46 . The program product according to claim 43 , wherein the second matrix M comprises
M
ij
=
{
1
,
i
=
j
1
-
2
(
1
-
p
i
)
l
-
2
(
1
-
p
j
)
l
+
4
(
1
-
p
i
-
p
j
)
l
,
i
≠
j
wherein p i and p j and l are from the probability model.
47 . The program product according to claim 43 , wherein the second matrix M comprises
M
ij
=
∑
[
j
1
+
…
+
j
t
=
l
]
log
j
i
log
j
j
(
l
j
1
…
j
t
)
p
1
j
1
…
p
t
j
t
wherein p i and p j and l are from the probability model.
48 . The program product according to claim 43 , wherein the second matrix M comprises
M
ij
=
{
(
l
(
l
-
1
)
p
i
2
+
lp
i
)
,
i
=
j
l
(
l
-
1
)
p
i
p
j
,
i
≠
j
wherein p i and p j and l are from the probability model.
49 . The program product according to claim 43 , wherein the second matrix M comprises
M
ij
=
∑
[
j
1
+
…
+
j
t
=
l
]
j
i
j
j
(
l
j
1
…
j
t
)
p
1
j
1
…
p
t
j
t
wherein p i and p j and l are from the probability model.
50 . The program product according to claim 43 , wherein the second matrix M comprises
M
ij
=
{
1
-
t
-
1
(
t
-
1
)
l
,
i
=
j
t
l
-
2
(
t
-
1
)
l
+
(
t
-
2
)
l
t
l
=
∑
k
=
0
t
-
3
(
t
-
3
k
)
(
t
-
k
-
1
)
!
S
(
l
+
1
,
t
-
k
)
t
l
,
i
≠
j
wherein t and l are from the probability model and S(n,k) are the Stirling numbers of the second kind.
51 . The program product according to claim 43 , wherein the step of computing traces of powers of the second matrix M comprises summing j+1 powers of eigenvalues of the second matrix M to obtain the value a j+1 for use in the recursive formula.
52 . A program product including a computer readable computer program encoded in a storage medium, the computer program executing an algorithm for computing an expected characteristic value of matrices created from a probability model comprising the steps of:
providing a probability model; and extrapolating from the probability model an expected characteristic value of matrices created from the probability model.
53 . The program product according to claim 52 , wherein the characteristic value is a singular value.
54 . The program product according to claim 52 , wherein the characteristic value is an eigenvalue.
55 . The program product according to claim 52 , wherein the probability model comprises:
a probability distribution corresponding to a set of elements; a probability distribution corresponding to a set of sample lengths; and a probability of a sample from the probability model.
56 . The program product according to claim 52 , wherein the step of extrapolating from the probability model comprises the steps of:
constructing a polynomial corresponding to the probability model; and extrapolating from the polynomial to obtain the characteristic value.
57 . The program product according to claim 56 , wherein the step of extrapolating from the polynomial comprises the steps of:
finding a root of the polynomial for the probability model; and extrapolating from the root of the polynomial to obtain the characteristic value.
58 . The program product according to claim 57 , wherein the step of extrapolating from the root of the polynomial comprises the steps of:
multiplying the root by an expected number of samples from the probability model; and taking the square root of the resulting value to obtain the characteristic value.
59 . The program product according to claim 56 , wherein the step of constructing the polynomial comprises the steps of:
computing one or more coefficients c i ; and dividing each computed coefficient c i by i! to obtain the polynomial
λ
t
-
c
1
1
!
λ
t
-
1
+
c
2
2
!
λ
t
-
2
-
…
±
c
t
t
!
λ
0
wherein each of the non-computed coefficients is set to zero and t is from the probability model.
60 . The program product according to claim 59 , wherein the step of computing a coefficient c i of the polynomial comprises computing a probabilistically weighted value
c
i
=
∑
l
c
i
(
l
)
prob
(
l
)
comprising an additional coefficient c i (l) corresponding to a length l and probability prob(l) from the probability model to obtain the coefficient c i .
61 . The program product according to claim 60 , wherein the step of computing the coefficient c i (l) of the polynomial for the length l comprises computing a determinant of a Gram matrix |B i T B i |, wherein B i is a matrix whose i columns are i copies of a column vector of probabilities from the probability model that depend on l, to obtain the coefficient c i (l).
62 . The program product according to claim 60 , wherein the step of computing the coefficient c i (l) of the polynomial for the length l comprises using a recursive formula to obtain the coefficient c i (l).
63 . The program product according to claim 62 , wherein the recursive formula comprises
c
n
+
1
(
l
)
=
∑
j
=
0
n
(
n
j
)
(
-
1
)
j
(
j
!
)
a
j
+
1
c
n
-
j
(
l
)
based on the length l, coefficients c n-j (l) with c 0 (l)=1, and traces of powers of a second matrix M wherein a n =trace(M n ).
64 . The program product according to claim 63 , wherein the second matrix M comprises expected values of products of pairs of probabilities according to the corresponding length/from the probability model.
65 . The program product according to claim 63 , wherein the second matrix M comprises
M
ij
=
{
1
-
(
1
-
p
i
)
l
,
i
=
j
1
-
(
1
-
p
i
)
l
-
(
1
-
p
j
)
l
-
(
1
-
p
i
-
p
j
)
l
,
i
≠
j
wherein p i and p j and l are from the probability model.
66 . The program product according to claim 63 , wherein the second matrix M comprises
M
ij
=
{
1
,
i
=
j
1
-
2
(
1
-
p
i
)
l
-
2
(
1
-
p
j
)
l
+
4
(
1
-
p
i
-
p
j
)
l
,
i
≠
j
wherein p i and p j and l are from the probability model.
67 . The program product according to claim 63 , wherein the second matrix M comprises
M
ij
=
∑
[
j
1
+
…
+
j
t
=
l
]
log
j
i
log
j
j
(
l
j
1
…
j
t
)
p
1
j
1
…
p
t
j
t
wherein p i and p j and l are from the probability model.
68 . The program product according to claim 63 , wherein the second matrix M comprises
M
ij
=
{
(
l
(
l
-
1
)
p
i
2
+
lp
i
)
,
i
=
j
l
(
l
-
1
)
p
i
p
j
,
i
≠
j
wherein p i and p j and l are from the probability model.
69 . The program product according to claim 63 , wherein the second matrix M comprises
M
ij
=
∑
[
j
1
+
…
+
j
t
=
l
]
j
i
j
j
(
l
j
1
…
j
t
)
p
1
j
1
…
p
t
j
t
wherein p i and p j and l are from the probability model.
70 . The program product according to claim 63 , wherein the second matrix M comprises
M
ij
=
{
1
-
t
-
1
(
t
-
1
)
l
,
i
=
j
t
l
-
2
(
t
-
1
)
l
+
(
t
-
2
)
l
t
l
=
∑
k
=
0
t
-
3
(
t
-
3
k
)
(
t
-
k
-
1
)
!
S
(
l
+
1
,
t
-
k
)
t
l
,
i
≠
j
wherein t and l are from the probability model and S(n,k) are the Stirling numbers of the second kind.
71 . The program product according to claim 63 , wherein the step of computing traces of powers of the second matrix M comprises summing j+1 powers of eigenvalues of the second matrix M to obtain the value a j−1 for use in the recursive formula.Join the waitlist — get patent alerts
Track US2010082643A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.