Plotting points that lie on the intersection of the given curves using gradient descent.

Overview

Plotting intersection of curves using gradient descent

Webapp Link ---> Streamlit App

What's the app about Why this app
Plotting functions and their intersection. An interesting application of gradient descent.
I'm a fan of plotting graphs (and visualizations in general).

Let's say you are giving equations of curves and you need to plot the intersection of these curves. As an example, say you have 2 spheres (3D), how would you plot the intersection of the given spheres?

... x, a & b are vectors of size 3.

My first approach to this problem was finding the equation of intersection of these 2 functions by equating them i.e. F_1(x) = F_2(x). Then trying to simplify the equation and use that equation to plot the points. This approach is not feasible for 2 reasons:

  1. Equating the 2 functions won't necessarily give you the equation of intersection. For instance, equating 2 equations of spheres will give you intersection plane of the spheres and not the equation of intersecting circle (if any).
  2. Even if you had an equation, the question still remains, how to plot points from a given equation?

If you observe, points that lie on the intersection of the curves should satisfy all the functions separately i.e.

So, another approach (highly ineffective) would be to generate points randomly everytime and see if they satisfy all the given equations. If it does, it is a valid 'point'. Else, generate another random point and repeat untill you have sufficient points. Downsides of this approach:

  1. The search space is too big. Even bigger for N-dimensional points.
  2. Highly ineffective approach. Might take forever to stumble upon such valid points.

Gradient Descent to the rescue

Can we modify the previous approach- Instead of discarding an invalid randomly generated point, can we update it iteratively so that it approaches a valid solution? If so, what would it mean to be a valid solution and when should we stop updating the sample?

What should be the criteria for a point x to be a valid solution?

If the point lies on the intersection of the curves, it should satisfy for all i i.e.

; &

We can define a function as the summation of the given functions to hold the above condition.

So, we can say that a point will be valid when it satisfies G(x) = 0, since it will only hold when all the F_i(x) are zero. This will be our criterion for checking if the point is a valid solution.

However, we are not yet done. The range of G(x) can be from . This means, the minimum value of G(x) is not necessarily 0. This is a problem because if we keep minimizing G(x) iteratively by updating x, the value of G(x) will cross 0 and approach a negative value (it's minima).

This could be solved if the minima of G(x) is 0 itself. This way we can keep updating x until G(x) approaches the minima (0 in this case). So, we need to do slight modification in G(x) such that its minimum value is 0.

My first instict was to define G(x) as the sum of absolute F_i(x) i.e.

The minimum value of this function will be 0 and will hold all the conditions discussed above. However, if we are trying to use Gradient Descent, using modulus operation can be problematic because the function may not remain smooth anymore.

So, what's an easy alternative for modulus operator which also holds the smoothness property? - Use squares!

This function can now be minimised to get the points of intersection of the curves.

  1. The function will be smooth and continuos. Provided F(x) are themselves smooth and continuous.
  2. The minimum value of G(x) is zero.
  3. The minimum value of G(x) represents the interesection of all F_i(x)
 Generate a random point x
 While G(x) != 0:
    x = x - lr * gradient(G(x))
    
 Repeat for N points.


Assumptions:

  1. Curves do intersect somewhere.
  2. The individual curves are themselves differentiable.
You might also like...
MNIST, but with Bezier curves instead of pixels
MNIST, but with Bezier curves instead of pixels

bezier-mnist This is a work-in-progress vector version of the MNIST dataset. Samples Here are some samples from the training set. Note that, while the

Code for the KDD 2021 paper 'Filtration Curves for Graph Representation'

Filtration Curves for Graph Representation This repository provides the code from the KDD'21 paper Filtration Curves for Graph Representation. Depende

CenterPoint  3D Object Detection and Tracking using center points in the bird-eye view.
CenterPoint 3D Object Detection and Tracking using center points in the bird-eye view.

CenterPoint 3D Object Detection and Tracking using center points in the bird-eye view. Center-based 3D Object Detection and Tracking, Tianwei Yin, Xin

Point Cloud Registration using Representative Overlapping Points.

Point Cloud Registration using Representative Overlapping Points (ROPNet) Abstract 3D point cloud registration is a fundamental task in robotics and c

Developed an optimized algorithm which finds the most optimal path between 2 points in a 3D Maze using various AI search techniques like BFS, DFS, UCS, Greedy BFS and A*

Developed an optimized algorithm which finds the most optimal path between 2 points in a 3D Maze using various AI search techniques like BFS, DFS, UCS, Greedy BFS and A*. The algorithm was extremely optimal running in ~15s to ~30s for search spaces as big as 10000000 nodes where a set of 18 actions could be performed at each node in the 3D Maze.

Visualize Camera's Pose Using Extrinsic Parameter by Plotting Pyramid Model on 3D Space
Visualize Camera's Pose Using Extrinsic Parameter by Plotting Pyramid Model on 3D Space

extrinsic2pyramid Visualize Camera's Pose Using Extrinsic Parameter by Plotting Pyramid Model on 3D Space Intro A very simple and straightforward modu

Image morphing without reference points by applying warp maps and optimizing over them.
Image morphing without reference points by applying warp maps and optimizing over them.

Differentiable Morphing Image morphing without reference points by applying warp maps and optimizing over them. Differentiable Morphing is machine lea

Code for Iso-Points: Optimizing Neural Implicit Surfaces with Hybrid Representations
Code for Iso-Points: Optimizing Neural Implicit Surfaces with Hybrid Representations

Implementation for Iso-Points (CVPR 2021) Official code for paper Iso-Points: Optimizing Neural Implicit Surfaces with Hybrid Representations paper |

(CVPR 2021) Back-tracing Representative Points for Voting-based 3D Object Detection in Point Clouds
(CVPR 2021) Back-tracing Representative Points for Voting-based 3D Object Detection in Point Clouds

BRNet Introduction This is a release of the code of our paper Back-tracing Representative Points for Voting-based 3D Object Detection in Point Clouds,

Video lie detector using xgboost - A video lie detector using OpenFace and xgboost

video_lie_detector_using_xgboost a video lie detector using OpenFace and xgboost

null 2 Jan 11, 2022
Training vision models with full-batch gradient descent and regularization

Stochastic Training is Not Necessary for Generalization -- Training competitive vision models without stochasticity This repository implements trainin

Jonas Geiping 32 Jan 6, 2023
Fibonacci Method Gradient Descent

An implementation of the Fibonacci method for gradient descent, featuring a TKinter GUI for inputting the function / parameters to be examined and a matplotlib plot of the function and results.

Emma 1 Jan 28, 2022
Alpha-IoU: A Family of Power Intersection over Union Losses for Bounding Box Regression

Alpha-IoU: A Family of Power Intersection over Union Losses for Bounding Box Regression YOLOv5 with alpha-IoU losses implemented in PyTorch. Example r

Jacobi(Jiabo He) 147 Dec 5, 2022
Given a 2D triangle mesh, we could randomly generate cloud points that fill in the triangle mesh

generate_cloud_points Given a 2D triangle mesh, we could randomly generate cloud points that fill in the triangle mesh. Run python disp_mesh.py Or you

Peng Yu 2 Dec 24, 2021
Implementation of Lie Transformer, Equivariant Self-Attention, in Pytorch

Lie Transformer - Pytorch (wip) Implementation of Lie Transformer, Equivariant Self-Attention, in Pytorch. Only the SE3 version will be present in thi

Phil Wang 78 Oct 26, 2022
Authors implementation of LieTransformer: Equivariant Self-Attention for Lie Groups

LieTransformer This repository contains the implementation of the LieTransformer used for experiments in the paper LieTransformer: Equivariant self-at

null 35 Oct 18, 2022
LieTransformer: Equivariant Self-Attention for Lie Groups

LieTransformer This repository contains the implementation of the LieTransformer used for experiments in the paper LieTransformer: Equivariant Self-At

OxCSML (Oxford Computational Statistics and Machine Learning) 50 Dec 28, 2022
Liecasadi - liecasadi implements Lie groups operation written in CasADi

liecasadi liecasadi implements Lie groups operation written in CasADi, mainly di

Artificial and Mechanical Intelligence 14 Nov 5, 2022