1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
import numpy as np
import cascade_creation
import itertools
from scipy import sparse
from scipy.sparse import linalg
def find_kth_rip_constants(M, k):
"""
Returns max(A_1, A_2) where:
1 + A_1 = arg max |Mx|_2^2 s.t. |x|_2 = 1 and |x|_0 = k
1 - A_2 = arg min |Mx|_2^2 s.t. |x|_2 = 1 and |x|_0 = kx
"""
delta = 0
print M.shape
for col_set in itertools.combinations(xrange(M.shape[1]), k):
M_kcol = M[:,list(col_set)]
delta_upper, delta_lower = upperlower_bound_rip(M_kcol)
delta = max(delta, max(delta_upper, delta_lower))
return delta
def upperlower_bound_rip(M):
"""
returns arg max/min |Mx|_2^2 s.t. |x|_2 = 1
which is the greatest eigenvalue value of M^T*M
or the square of the greatest singular value of M
"""
M = sparse.csc_matrix(M)
s_upper = linalg.svds(M, 1, tol=.01, which ='LM', maxiter = 2000,
return_singular_vectors=False)
s_lower = linalg.svds(M, 1, tol=.01, which = 'SM', maxiter= 2000,
return_singular_vectors=False)
return s_upper ** 2 - 1, 1 -s_lower ** 2
def test():
"""
unit test
"""
G = cascade_creation.InfluenceGraph(max_proba=.3)
G.erdos_init(n=10, p =1)
cascades = cascade_creation.generate_cascades(G, p_init=.3, n_cascades=10)
M, __ = cascade_creation.icc_matrixvector_for_node(cascades, None)
M = cascade_creation.normalize_matrix(M)
print find_kth_rip_constants(M, 5)
if __name__=="__main__":
test()
|
