-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathREADME
174 lines (111 loc) · 6.13 KB
/
README
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
This package contains functions for computing signal projections into the
EMD-model (with variations).
================================================================================
Table of contents:
1. Installation
2. Background
3. Usage
4. Contact
5. License
================================================================================
1. Installation
1.1 Matlab module
Compile the mex file with
make mexfile
which will produce a file emdflow.<mex-extension>, where <mex-extension> is the
mex file name extension of your system.
Currently the only dependency is mex, the Matlab module compiler, which needs to
be installed on your system. Note that mex requires g++ on UNIX systems.
The makefile assumes that mex is available on the command line as mex. If this
is not the case on your system, you can override the path to the mex compiler:
make MEX='/path/to/mex' mexfile
1.2 Command-line program
The package also contains a command-line program for testing purposes. You can
compile it with
make emd_flow
Note that the emd_flow binary depends on the boost library (in particular, the
program options library).
1.3 Unit tests
You can build and execute the unit tests for the main emd_flow routine with
make run_emd_flow_test
The unit tests are mainly for development purposes. In order to run the unit
tests, you need the boost library (headers only is sufficient) and the Google
C++ test framework googletest, which you can get from:
http://code.google.com/p/googletest/
On Ubuntu / Debian, you can install googletest via the libgtest-dev package.
In that case, the makefile should find you googletest installation. Otherwise,
you can specify the path to your local googletest installation with
make GTESTDIR='/path/to/googletest' run_emd_flow_test
================================================================================
2. Background
See "The Constrained Earth Mover Distance Model, with Applications to
Compressive Sensing" (L. Schmidt, C. Hegde, P. Indyk):
http://people.csail.mit.edu/indyk/main_sampta13.pdf
================================================================================
3. Usage
3.1 Matlab module
The name of the function is emd_flow. It requires at least three parameters:
- X, a 2D-matrix containing the signal amplitudes.
Note that the algorithm works with the absolute values of X directly
without squaring the amplitudes first. So if you want to get an
l2-guarantee, pass X.^2 into emd_flow.
- s, the per-column sparsity of the resulting projection.
- B, the EMD budget. B can be either a single value or an interval [B_low,
B_high]. For a single value, emd_flow tries to find the best signal
using at most an EMD-budget B. For an interval, emd_flow tries to find a
signal approximation using at least B_low EMD-budget and at most B_high
EMD-budget. Specifying an interval instead of a single value can speed up
the convergence of the algorithm considerably.
Moreover, emd_flow accepts an optional fourth parameter opts, which can
specify a number of additional options:
- opts.verbose, a boolean flag that indicates whether emd_flow shoud provide
verbose output. Default: false.
- opts.lambda_low, the initial guess for the lower bound on the Lagrangian
relaxation parameter lambda. An incorrect guess will be corrected by the
algorithm. A good guess for lambda_low can speed up the convergence of the
algorithm considerably. A good source for a guess for lambda_low is a previous
run of lambda_low with similar parameters. Default: 0.5.
- opts.lambda_high, the initial guess for the upper bound on the Lagrangian
relaxation parameter lambda. As with lambda_low, an incorrect guess will be
corrected by the algorithm and a good guess can speed up the convergence of
the algorithm considerably. Default: 1.0.
- opts.num_iterations, the maximum number of iterations the algorithm performs
in the binary search over lambda. Note that the initial iterations for finding
correct values for lambda_low and lambda_high do not count towards this
number. Default: 10.
- opts.outdegree_vertical_distance, the maximum vertical distance for edges
between columns. This restricts the maximum outdegree of each node to
2 * opts.outdegree_vertical_distance + 1. If the value is set to -1, the
outdegree of the nodes is not limited (each node is fully connected to the
next layer). Default: -1.
- opts.emd_costs, the EMD costs of the edges between columns. Has to be a
row vector with opts.outdegree_vertical_distance + 1 entries, unless
opts.outdegree_vertical_distance is -1, in which case the vector needs to
have num_rows - 1 entries.
Entry i in the vector gives the cost of an edge between columns with
vertical distance i-1.
The vector can also be empty, in which case the standard EMD weights are
used ([0, 1, 2, 3, ...]). Default: [] (empty).
After a successful run of emd_flow, the algorithm returns the following values:
[support, emd_cost, amp_sum, final_lambda_low, final_lambda_high]
- support is a 2D-matrix with the same dimensions as the input parameter X.
Each entry in support is either 0 or 1, indicating whether the corresponding
entry of X is part of the support or not.
- emd_cost is the total EMD-cost of the support identified by emd_flow.
- amp_sum is the sum of absolute values of the supported entries in X.
- final_lambda_low is the lower bound on lambda in the last iteration of the
binary search. If you run emd_flow several times on similar inputs, consider
using this value as an initial guess for lambda_low in order to speed up
convergence.
- final_lambda_high is the lower bound on lambda in the last iteration of the
binary search. If you run emd_flow several times on similar inputs, consider
using this value as an initial guess for lambda_high in order to speed up
convergence.
================================================================================
4. Contact
For questions, comments, etc. about this package, contact Ludwig Schmidt
================================================================================
5. License
This package is licensed under the MIT license. See the file LICENSE for
details.