1 files changed, 49 insertions, 0 deletions
diff --git a/src/rip_condition.py b/src/rip_condition.py
new file mode 100644
index 0000000..fccf9a4
--- /dev/null
+++ b/src/rip_condition.py
@@ -0,0 +1,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()